Tưới ruộng
Đề bài
Tưới ruộng – FARM.* Trên khu đất ruộng hình chữ nhật, được chia thành từng thửa vuông đều nhau có cạnh là một đơn vị để cho các tá điền thuê lại trồng trọt. Tại một số thửa ruộng, bạn Bờm cho đào giếng để lấy nước tưới. Vì năm nay trời hạn nên mỗi giếng chỉ đủ nước để tưới cho các thửa ruộng xung quanh trong phạm vi bán kính 2 ô vuông đơn vị. Các tá điền không thể đưa nước đi xa vì họ không có dụng cụ cũng không đủ sức đưa đi.
Yêu cầu: hãy đếm xem có bao nhiêu thửa ruộng sẽ không tưới được.
Ví dụ: với diện tích ruộng $6 \times 9$ như hình bên dưới có 3 giếng nước tại các ô ở dòng 2 cột 6, dòng 3 cột 2 và dòng 5 cột 7. Các ô tô đen chính là những ô không thể tưới.
Dữ liệu vào: trong tập tin văn bản FARM.INP gồm:
- Dòng đầu là hai số nguyên dương $M$ và $N$ cách nhau một dấu cách cho biết kích thước khu đất $(1 < M, N \le 100)$;
- Dòng thứ hai là một số nguyên dương $K$ cho biết số giếng đã đào trên khu đất;
- Trên $K$ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương tương ứng với chỉ số dòng và cột của từng giếng đào trên khu đất, các số cách nhau một dấu cách. Chỉ số dòng được đánh số từ 1, tính từ trên xuống dưới của bảng. Chỉ số cột được đánh số từ 1, tính từ trái sang phải của bảng $(0 \le K \le 10^4)$.
Kết quả: ghi vào tập tin văn bản FARM.OUT gồm một số nguyên duy nhất là số thửa ruộng không thể tưới.
6 9
3
2 6
3 2
5 76Lưu ý trên CLUE OJ: (1) bài này không nhập/xuất chuẩn mà đọc file FARM.INP, ghi file FARM.OUT đúng tên như đề thi; (2) mỗi bạn chỉ được nộp 1 lần duy nhất, nên hãy kiểm tra thật kỹ trước khi bấm nộp. Code trong bài dùng mẹo if (fopen("FARM.INP", "r")): có file thì đọc/ghi file, không có thì đọc bàn phím – in màn hình, nên vừa chạy thử trên máy vừa nộp bài được luôn.
Lời mở đầu
Bài 2 đề HSG Tin 9 TP.HCM năm 2018. Chỗ cần suy nghĩ duy nhất là hiểu cho đúng cụm từ "bán kính 2 ô"; hiểu đúng rồi thì bài là một bài đánh dấu trên mảng 2 chiều rất cơ bản. Vì chỉ được nộp 1 lần nên mình sẽ làm 2 cách để kiểm tra chéo nhau, và chạy thật cả 2 cách trên bộ test chính thức.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test. Đề không chia subtask, và thật ra mọi test đều nhỏ: $M, N \le 100$ và số giếng nhiều nhất chỉ 532 (đề cho phép tới $10^4$).
| Test | M | N | K (số giếng) | Đáp án | Ghi chú |
|---|---|---|---|---|---|
| 1 – 30 | 2 – 28 | 1 – 23 | 0 – 27 | 0 – 137 | Nhỏ |
| 31 – 60 | 1 – 48 | 5 – 54 | 2 – 75 | 12 – 1355 | Vừa |
| 61 – 100 | 1 – 100 | 3 – 100 | 0 – 532 | 18 – 4149 | Lớn hơn (test 100 là 100 × 100) |
Mấy điều đáng chú ý khi mình soi bộ test:
- Có 8 test với $K = 0$ (test 2, 4, 7, 10, 18, 19, 24, 84): không có giếng nào, đáp án là $M \times N$. Code phải xử lý được trường hợp này (vòng lặp đọc giếng chạy 0 lần).
- Đề ghi $1 < M, N$ nhưng có 5 test có $M = 1$ hoặc $N = 1$ (test 7, 10, 25, 56, 95) – khu đất chỉ là 1 hàng hoặc 1 cột. Code dùng
max/minđể cắt vùng tưới thì vẫn chạy đúng. - Mọi giếng đều nằm trong khu đất và không có 2 giếng trùng vị trí.
Vì bộ test nhỏ nên cả 2 cách bên dưới (kể cả cách xét từng thửa) đều qua hết. Tuy vậy mình vẫn phân tích trường hợp xấu nhất theo đề ($K = 10^4$) để các bạn biết cách nào an toàn hơn khi đi thi.
Ý tưởng"Bán kính 2 ô" là hình vuông 5 × 5
Nhìn hình ví dụ: giếng ở dòng 3 cột 2 tưới được cả ô dòng 1 cột 4 (lệch 2 dòng và 2 cột, tức là đi chéo). Còn ô dòng 6 cột 1 không được tưới vì lệch tới 3 dòng. Vậy "bán kính 2 ô" ở đây nghĩa là:
Tức là mỗi giếng tưới một hình vuông 5 × 5 có tâm là giếng (bị cắt bớt nếu giếng ở gần mép khu đất).
Mình kiểm tra lại ví dụ: giếng $(2, 6)$ tưới dòng 1–4, cột 4–8; giếng $(3, 2)$ tưới dòng 1–5, cột 1–4; giếng $(5, 7)$ tưới dòng 3–6, cột 5–9. Còn lại đúng 6 ô khô: ô $(1, 9)$, $(2, 9)$ và 4 ô $(6, 1)$ … $(6, 4)$ – khớp với hình ✓. Mình cũng đã kiểm tra cách hiểu này khớp với đáp án của cả 100 test.
Em nhập kích thước và vị trí các giếng rồi bấm Tiếp để xem từng giếng tưới vùng nào (ô xanh đậm là ô vừa được tưới thêm):
Cách 1Xét từng thửa ruộng – O(M·N·K)
Cách nghĩ trực tiếp nhất: với mỗi thửa $(x, y)$, duyệt qua tất cả $K$ giếng xem có giếng nào đủ gần không. Không có giếng nào thì thửa đó khô, tăng biến đếm.
- Biến
wetđặt lại bằngfalsecho từng thửa. Gặp được 1 giếng đủ gần làbreakluôn, không cần xét các giếng còn lại. - Hàm
abslấy giá trị tuyệt đối, viết điều kiện $|x - r| \le 2$ và $|y - c| \le 2$ rất gọn. - Chỉ cần lưu toạ độ các giếng vào 2 mảng
r[],c[], không cần mảng 2 chiều cho khu ruộng.
Theo đề, trường hợp xấu nhất là $M = N = 100$, $K = 10^4$: khoảng $10^4 \times 10^4 = 10^8$ phép so sánh. Mình tự tạo thử một test như vậy (mọi giếng dồn vào 1 góc để hầu hết thửa ruộng phải xét hết $10^4$ giếng): bản C++ vẫn chạy khoảng 0,09 giây, nhưng bản Python thì mất hơn 7 giây – quá chậm.
Cách 2Đánh dấu vùng tưới của từng giếng – O(25·K + M·N)
Đảo ngược cách nhìn: thay vì mỗi thửa đi tìm giếng, ta để mỗi giếng tự đánh dấu các thửa mà nó tưới được vào mảng wet. Mỗi giếng chỉ đánh dấu tối đa $5 \times 5 = 25$ ô. Cuối cùng đếm số ô chưa bị đánh dấu.
- Phần dòng của hình vuông là từ $r - 2$ tới $r + 2$, nhưng phải cắt vào trong khu đất:
max(1, r - 2)đếnmin(m, r + 2). Tương tự cho cột. Nhờ vậy giếng ở sát mép không làm ghi ra ngoài mảng. - Nhiều giếng có vùng tưới chồng lên nhau cũng không sao: ô đã
truegántruelần nữa vẫn làtrue, không bị đếm trùng. - Mảng
wetkhai báo toàn cục nên ban đầu tất cả làfalse.
Với test xấu nhất tự tạo ở trên ($K = 10^4$) cách 2 chỉ tốn khoảng $25 \cdot 10^4 + 10^4$ phép gán: bản C++ chạy khoảng 0,01 giây, bản Python khoảng 0,04 giây.
Tổng kếtSo sánh 2 cách
| Cách | Độ phức tạp | C++ | Python | Test xấu nhất theo đề |
|---|---|---|---|---|
| 1. Xét từng thửa | $O(M \cdot N \cdot K)$ | 100/100 | 100/100 | C++ ổn, Python quá chậm |
| 2. Đánh dấu 5 × 5 | $O(25K + M \cdot N)$ | 100/100 | 100/100 | Cả 2 đều rất nhanh |
FARM.INP, FARM.OUT.