Mình hiện tại đang giải một bài toán mảng 2 chiều với yêu cầu có độ dài mảng <=10^6 10^6.Khi thử với test case <10^3 thì chạy bình thường nhưng khi chạy 10^4 trở lên thì bị lỗi RTE,mọi người giúp mình với.
C++ cách để khai báo một mảng 2 chiều có độ dài [10^6][10^6]
Đề bài đầy đủ của bạn đâu?
mình gửi link bài
mình mới cập nhật ở trên lại đó bạn.
Bạn có thể cho mình biết RTE mà bạn gặp phải là gì không?
[ [10^6][10^6] ~ 1000000 x 1000000 ~1 Tera or a trillion For an int value it’s too big. You should work with long value
Bạn bị đề bài lừa rồi. Bài này không dùng mảng 2 chiều 1e6 * 1e6 được, bạn phải nghĩ ra công thức toán thôi.
Bạn có công thức QHĐ chưa?
1 Like
Bài này có thể chứng minh có thể tô không ít hơn K \times K màu: (1)
- Vì nếu ô (x, y) được tô thì ít nhất các ô (x+i, y+j)\;với\; 0 \le i, j < K phải tô khác màu nhau để thoã mãn điều kiện. Vậy với m,n \geq K thì phải tô \geq K\times K màu.
Có thể chỉ ra một cách dùng đúng K \times K màu để tô: (2)
- Có thể tô màu bằng cách lặp lại pattern bằng cách xây dựng bảng K\times K bất kì rồi lát bảng màu này cho ma trận m\times n.
Từ (1) và (2) thì kết quả bài toán = K \times K
Khoan, m \le K \;\text{hoặc}\; n \le K thì sao? Lúc đấy viên gạch cơ bản sẽ có kích thước \min(m, K) \times \min(n,K) do chiều dài mỗi cạnh không vượt quá m, n. Đây cũng là kết quả bài toán.
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?