Tree (Tin học trẻ toàn quốc 2024 – Vòng sơ khảo – Bảng B, C1, C2)
Đề bài
Alice có một khu đất trống được chia làm $m \times n$ mảnh đất hình vuông. Các hàng mảnh đất hình vuông được đánh số từ $1$ đến $m$ từ trên xuống dưới, các cột mảnh đất hình vuông được đánh số từ $1$ đến $n$ từ trái sang phải. Mảnh đất hình vuông nằm giao giữa hàng $i$ $(1 \le i \le m)$ và cột $j$ $(1 \le j \le n)$ gọi là ô $(i, j)$.
Alice dự định sẽ đi lần lượt từng ô theo đường xoắn ốc cùng chiều kim đồng hồ bắt đầu từ ô $(1, 1)$ để trồng cây trên các mảnh đất hình vuông. Ví dụ, với khu đất $4 \times 5$ thì thứ tự các ô Alice đi như hình bên trái.
Qua khảo sát, Alice biết rằng có $k$ ô $(x_1, y_1),$ $(x_2, y_2),$ $\ldots,$ $(x_k, y_k)$ không thể trồng cây. Khi đó, nếu Alice đi vào các ô này Alice sẽ bỏ qua và không trồng cây ở đó. Là một người yêu thích toán học, Alice mong muốn mỗi ô sẽ được trồng một số cây đều là số nguyên tố.
Cụ thể, khi đi theo đường xoắn ốc như dự định, nếu vào ô $(u, v)$ là ô trồng được cây và ô này là ô thứ $t$ trồng được cây (tính từ lúc bắt đầu xuất phát) thì ô $(u, v)$ sẽ được trồng số lượng cây là số nguyên tố lớn thứ $t$ (tức số nguyên tố thứ $t$ tính từ nhỏ đến lớn: $2, 3, 5, 7, \ldots$). Ví dụ, nếu khu đất $4 \times 5$ có 7 ô không thể trồng được cây là $(1,2),$ $(2,3),$ $(3,4),$ $(4,5),$ $(2,1),$ $(3,2),$ $(4,3)$ thì số cây được trồng tại các ô như hình bên phải.
Sau khi trồng cây xong, Alice muốn tính số lượng cây nằm trong hình chữ nhật có ô trái trên là ô $(u_1, v_1)$ và ô phải dưới là ô $(u_2, v_2)$. Hãy giúp Alice trả lời $q$ câu hỏi như vậy.
Input:
- Dòng đầu chứa bốn số nguyên $m, n, k, q$ $(m, n \le 500;\ k \le m \times n;\ q \le 10^6)$.
- Dòng thứ $i$ trong $k$ dòng sau chứa hai số nguyên $x_i, y_i$ $(1 \le x_i \le m;\ 1 \le y_i \le n)$.
- Tiếp theo là $q$ dòng, mỗi dòng chứa bốn số $u_1, v_1, u_2, v_2$ mô tả một câu hỏi.
Output: gồm $q$ dòng, mỗi dòng là câu trả lời cho câu hỏi tương ứng ở dữ liệu vào.
Subtask:
- Subtask 1 (30% số điểm): $m = 1;\ n \le 100$.
- Subtask 2 (30% số điểm): $m \le 100;\ n \le 100$.
- Subtask 3 (20% số điểm): $q \le 10$.
- Subtask 4 (20% số điểm): không có ràng buộc nào thêm.
4 5 7 2
1 2
2 3
3 4
4 5
2 1
3 2
4 3
1 1 2 2
3 2 4 333
60Giải thích ví dụ: câu hỏi 1 là hình chữ nhật $(1,1)$–$(2,2)$ gồm các ô $2 + 0 + 0 + 31 = 33$ cây. Câu hỏi 2 là hình chữ nhật $(3,2)$–$(4,3)$ gồm $0 + 41 + 19 + 0 = 60$ cây.
Lời mở đầu
Đây là một bài rất "đủ món" của chương Mảng 2 chiều: phải đi xoắn ốc trên lưới, phải sinh số nguyên tố thật nhanh, và cuối cùng phải trả lời tới $10^6$ câu hỏi tổng hình chữ nhật. Mỗi món riêng lẻ đều không khó, nhưng ghép lại thì rất dễ bị quá thời gian ở một khâu nào đó. Mình sẽ đi từ cách làm "thẳng như đề nói" (ăn 2 subtask đầu) rồi lần lượt gỡ từng nút thắt để đạt trọn điểm, và tất cả các cách đều được mình chạy thật 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, chia đúng theo 4 subtask của đề (mỗi test 1% số điểm). Mình đã đọc từng test và thống kê lại:
| Test | m | n | k | q | Số ô trồng được (max) | Số test có ô cấm lặp lại | Đáp án lớn nhất |
|---|---|---|---|---|---|---|---|
| 1 – 30 | 1 | 21 … 100 | 1 … 97 | 5 … 10000 | 99 | 13 | 23 590 |
| 31 – 60 | 3 … 100 | 3 … 100 | 1 … 8991 | 5 … 10000 | 9 999 | 14 | 493 632 640 |
| 61 – 80 | 11 … 500 | 10 … 500 | 1 … 80805 | 10 | 249 912 | 12 | 334 166 215 100 |
| 81 – 100 | 20 … 500 | 21 … 500 | 0 … 250000 | 100000 … 1000000 | 250 000 | 9 | 420 257 213 289 |
Những điểm đáng chú ý:
- Test 1 – 30 đều có $m = 1$ (Subtask 1), test 31 – 60 có $m, n \le 100$ (Subtask 2), test 61 – 80 có đúng $q = 10$ (Subtask 3, trong đó test 76 – 80 là lưới $500 \times 500$), test 81 – 100 là Subtask 4 với $q$ từ $10^5$ đến $10^6$.
- Danh sách ô không trồng được có thể lặp lại cùng một ô. Ví dụ test 100 có $k = 250\,000 = m \times n$ nhưng thật ra chỉ có 157 953 ô khác nhau bị cấm. Ai lấy "$m \times n - k$" làm số ô trồng được là sai ngay. Còn test 99 thì $k = 0$.
- Có test có tới $250\,000$ ô trồng được → cần đến số nguyên tố thứ 250 000 là $3\,497\,861$.
- Đáp án lớn nhất khoảng $4{,}2 \cdot 10^{11}$, vượt xa
int→ bắt buộc dùnglong long. - Mọi câu hỏi đều hợp lệ: $u_1 \le u_2$, $v_1 \le v_2$.
Bảng subtask và cách giải nào ăn được subtask nào (kết quả chạy thật ở các phần bên dưới):
| Subtask | Điều kiện | Test | Cách 1 | Cách 2 | Cách 3 |
|---|---|---|---|---|---|
| 1 (30%) | $m = 1;\ n \le 100$ | 1 – 30 | ✔ | ✔ | ✔ |
| 2 (30%) | $m, n \le 100$ | 31 – 60 | ✔ | ✔ | ✔ |
| 3 (20%) | $q \le 10$ | 61 – 80 | ⚠ sát giới hạn | ✔ | ✔ |
| 4 (20%) | không ràng buộc thêm | 81 – 100 | ✘ (10/20 test) | ✔ | ✔ |
Ý tưởngBa việc phải làm
Bài toán tách được thành 3 việc độc lập, mình giải quyết lần lượt từng việc:
- Đi xoắn ốc để biết thứ tự các ô.
- Ô trồng được thứ $t$ thì trồng số nguyên tố thứ $t$ → cần sinh đủ số nguyên tố.
- Trả lời $q$ câu hỏi tổng các ô trong hình chữ nhật.
Việc 1: đi xoắn ốc như một chú robot
Thay vì tính công thức phức tạp, mình cho một "chú robot" đứng ở ô $(1, 1)$, quay mặt sang phải, rồi lặp lại $m \times n$ lần:
- Xử lý ô đang đứng (trồng cây nếu trồng được) và đánh dấu ô này đã đi qua.
- Nhìn ô phía trước mặt. Nếu ô đó ra ngoài khu đất hoặc đã đi qua rồi thì rẽ phải (phải → xuống → trái → lên → phải ...).
- Bước tới ô phía trước.
4 hướng theo chiều kim đồng hồ được lưu trong 2 mảng dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; "rẽ phải" chỉ là d = (d + 1) % 4. Đây cũng chính là kỹ thuật mình đã dùng trong bài ma trận xoắn ốc.
Việc 2: số nguyên tố thứ t
Đi tới ô trồng được thì tăng biến đếm $t$ và trồng số nguyên tố thứ $t$. Có tối đa $500 \times 500 = 250\,000$ ô trồng được, mà số nguyên tố thứ 250 000 là 3 497 861. Vậy ta cần sinh các số nguyên tố tới khoảng $3{,}5$ triệu. Ô không trồng được thì có $0$ cây.
Em nhập kích thước và danh sách ô cấm (mỗi ô là "hàng cột", các ô cách nhau dấu phẩy) rồi bấm Tiếp để xem robot đi và trồng cây:
Việc 3: tổng hình chữ nhật bằng mảng cộng dồn 2 chiều
Gọi $a[i][j]$ là số cây ở ô $(i, j)$. Ta tính trước mảng
Khi đó tổng hình chữ nhật $(u_1, v_1)$–$(u_2, v_2)$ là
Em nhập câu hỏi rồi bấm Tiếp: phần đầu xem cách tính từng ô của $f$, phần sau xem 4 hình chữ nhật cộng trừ với nhau ra sao:
Cách 1Làm đúng như đề nói – ăn Subtask 1, 2
Cách đầu tiên ai cũng nghĩ ra: đi xoắn ốc, mỗi lần cần số nguyên tố mới thì tăng dần p và thử chia để kiểm tra nguyên tố, còn mỗi câu hỏi thì cộng từng ô trong hình chữ nhật bằng 2 vòng lặp lồng nhau.
- Mảng
cam[][]đánh dấu ô không trồng được. Bộ test có những dòng ô cấm bị lặp lại (xem bảng thống kê), dùng mảng đánh dấu thì lặp bao nhiêu lần cũng không sao. - Mảng
tham[][]đánh dấu ô robot đã đi, để biết khi nào phải rẽ. Điều kiện ra ngoài khu đất được đặt trướctham[nx][ny]trong phép||. do p++; while(!laNT(p));: tăng $p$ cho tới khi gặp số nguyên tố tiếp theo. Biếnpbắt đầu từ 1 nên lần đầu sẽ được 2.- Tổng có thể lên tới khoảng $4{,}2 \cdot 10^{11}$ nên
avàsphải làlong long.
Kết quả chạy thật: bản C++ đúng 90/100 test. Qua trọn Subtask 1, 2 và cả 10 test 81 – 90 (lưới nhỏ, $q = 10^5$). Tuy nhiên 5 test lưới $500 \times 500$ của Subtask 3 (test 76 – 80) mất 0,55 – 0,89 giây chỉ để thử chia tìm số nguyên tố – sát nút giới hạn 1 giây, gặp máy chấm chậm hơn là quá thời gian ngay. Cả 10 test 91 – 100 (lưới $500 \times 500$, $q \ge 10^5$) đều quá thời gian. Bản Python đúng 82/100: ngoài test 91 – 100 còn quá thời gian ở test 76 – 80, 81, 88, 89.
- Câu hỏi được cộng từng ô nên mất tới $m \times n$ phép cộng cho một câu hỏi. Với $q = 10^6$ và lưới $500 \times 500$ là $2{,}5 \cdot 10^{11}$ phép tính – không thể kịp.
- Ở các test Subtask 3 lưới $500 \times 500$, dù chỉ có 10 câu hỏi nhưng chương trình vẫn chạy gần hết 1 giây: thủ phạm là khâu thử chia để tìm tới 250 000 số nguyên tố (mỗi số thử chia tới $\sqrt{p} \approx 1870$). Qua được hay không phụ thuộc vào độ nhanh của máy chấm – không nên mạo hiểm.
Cách 2Sàng nguyên tố + cộng dồn 2 chiều – đủ 4 subtask
Gỡ 2 nút thắt của cách 1:
- Sinh số nguyên tố bằng sàng Eratosthenes tới $3{,}6 \cdot 10^6$: mỗi số nguyên tố $i$ gạch bỏ các bội $i^2, i^2 + i, \ldots$, chỉ mất khoảng $O(V \log \log V)$. Các số còn lại cho vào vector
pr, ô trồng được thứ $t$ (đếm từ 0) nhậnpr[t]. - Tính mảng cộng dồn
fmột lần $O(m \cdot n)$, mỗi câu hỏi chỉ còn 4 phép cộng trừ.
MAXV = 3600000 thành MAXV = 50 (sàng ra 15 số nguyên tố), nên em cho tối đa 15 ô trồng được. Phần còn lại giữ nguyên code.- Mảng
hop[]3,6 triệu phần tửboolchỉ tốn khoảng 3,6 MB, nhớ khai báo toàn cục (khai báo trong hàmmaindễ bị tràn bộ nhớ ngăn xếp). jkhai báolong longvìi * ivới $i$ gần $3{,}6 \cdot 10^6$ sẽ trànint.- Hàng 0 và cột 0 của
fbằng 0 (mảng toàn cục), nên công thức đúng luôn cả khi $u_1 = 1$ hoặc $v_1 = 1$.
Kết quả chạy thật: bản C++ đúng 100/100 test, test chậm nhất (test 99) chạy khoảng 0,33 giây. Bản Python (sàng vừa đủ số ô trồng được, đọc dữ liệu bằng sys.stdin.buffer) đúng 95/100: 5 test cuối có $q = 10^6$ mất 1,25 – 1,46 giây – thuật toán đúng, chỉ là Python không kịp xử lý một triệu câu hỏi trong 1 giây.
Cách 3Thêm nhập xuất nhanh cho 10^6 câu hỏi
Thuật toán đã tối ưu, nhưng file test lớn nhất nặng khoảng 15 MB (gần 4,5 triệu số cần đọc và $10^6$ dòng cần in). Lúc này phần lớn thời gian chạy là đọc và in. Để chắc chắn an toàn, mình tự viết hàm readInt() đọc cả khối dữ liệu bằng fread rồi tự tách số, và gom toàn bộ kết quả vào một chuỗi rồi in ra một lần bằng fwrite. Phần thuật toán giữ nguyên như cách 2.
MAXV = 3600000 thành MAXV = 50 (sàng ra 15 số nguyên tố), nên em cho tối đa 15 ô trồng được. Phần còn lại giữ nguyên code. Hàm gc(), readInt() chỉ là "máy đọc số", khung chạy tay coi mỗi lần gọi là một bước.Kết quả chạy thật: bản C++ đúng 100/100 test, test chậm nhất chỉ còn khoảng 0,15 giây – nhanh hơn cách 2 hơn 2 lần, và phần lớn thời gian còn lại là của khâu sàng nguyên tố.
Nhận xét
Đăng nhận xét