01/10/2018, 00:52
Bài toán đếm số ô đã đi qua
Luka tìm thấy một bàn cờ rất lạ trong căn gác của mình. Nó bao gồm R×C ô vuông và các hàng được đánh số từ 0 đến R-1 theo chiều từ trên xuống dưới và các cột đánh số từ 0 đến C-1 theo chiều từ trái sang phải. Các ô trong bản đều
được tô bằng một trong hai màu: xám hoặc trắng.
Màu trắng: nếu trong biểu diễn ở hệ nhị phân số hàng và số cột của ô này có ít nhất một chữ số 1 tại cùng một vị trí.
Ví dụ, ô (4, 5) sẽ có màu trắng.
Màu xám, nếu ngược lại. Ví dụ, ô (2, 5) tô màu xám.
Chú nhím của Luka thích đi bộ trên cái bảng đó và hiện nó đang đi một cách bất thường. Nó bắt đầu đi bộ từ ô (0, 0)
và tiếp tục đi theo hình zig-zag. trong khi đó Luka đếm xem có bao nhiêu hình vuông màu xám mà chú nhím đã đi
qua.
Sau khi nhím đi được K ô vuông thì nó đã mệt mỏi và ngủ thiếp đi. Luka sau đó cũng đi ngủ. Thật vui khi Luka đã có
thể đếm được hết các ô vuông màu xám. Biết kích thước của bảng và số K cho trước. Nhiệm vụ của bạn là viết chương
trình đếm.
INPUT
Dòng đầu tiên chứa hai số nguyên R (1 ≤ R ≤ 1 000 000) và C (1 ≤ C ≤ 1 000 000) là kích thước của bảng. Dòng thứ
hai chứa số nguyên K (1 ≤ K ≤ R × C) - tổng số ô vuông mà chú nhim đã đi qua. Lưu ý rằng con số này có thể không
phù hợp với một số nguyên 32-bit.
50% số test có K < 1000000.
OUTPUT
Số lượng các ô màu xám mà chú nhím đã đi qua.
Mọi người cho mình ý tưởng bài này. Hãy cho ý tưởng thôi, đừng code. Mình cảm ơn nhiều.
Bài liên quan
Có 2 vấn đề cần giải quyết
1/ Cách kiểm tra ô trắng hay xám
Đề yêu cầu nếu có bit 1 trùng vị trí nhau thì là trắng còn lại là xám.
Nhớ lại phép logic AND trả về 1 khi và chỉ khi cả 2 đều 1.
-> Vậy nếu a & b mà trả về 1 số != 0 thì ít nhiều là có bit 1 trùng nhau.
Vậy check ô xám thì chỉ cần kiểm tra giá trị của a & b là được.
2/ Quy luật của đường đi zigzag.
Bạn có thể tham khảo ở đây:
https://quickgrid.wordpress.com/tag/zig-zag-2d-array-traversal/
Nôm na là vầy:
Ghi ra giấy đường đi
(0,0) (1,0) (0,1) (0,2) (1,1) (2,0) (3, 0) …
Dễ thấy có 4 khả năng
dòng = 0 mà cột chẵn -> đi sang 1 đơn vị (2,0 -> 3,0)
cột lẻ, dòng = 0 -> đi xéo xuống khi nào cột = 0 (3,0 -> 2,1 -> 1,2 -> 0,3)
cột = 0 mà dòng lẻ -> đi xuống 1 đơn vị (0,1 -> 0,2)
cột = 0, dòng chẵn -> đi xéo lên tới khi nào dòng = 0 (0,2 -> 1,1 -> 2,0)
Tuy nhiên cách trên chỉ áp dụng cho 1/2 ma trận nhưng mình nghĩ bạn có thể tự suy đoán quy luật của 1/2 ma trận còn lại dựa vào cái trên
Cảm ơn bạn nhiều !!!