Thành phố (CITY)
Đề bài
Đề tuyển sinh lớp 10 trường Phổ thông Năng khiếu năm 2012 – 2013.
Bản đồ hành tinh Alpha được chia thành lưới ô vuông có kích thước gồm $m$ dòng và $n$ cột. Các dòng đánh số từ trên xuống dưới, các cột được đánh số từ trái qua phải và đều bắt đầu từ 1. Hai ô gọi là kề nhau nếu có chung cạnh hoặc chung đỉnh. Như vậy, mỗi ô kề với tối đa 8 ô.
Ô ở dòng $i$, cột $j$ có khả năng sản xuất $a_{i,j}$ đơn vị lương thực trong mỗi tháng với $0 \le a_{i,j} \le 10^6$.
Một khu dân cư được xây dựng trong một ô bất kỳ trên bản đồ sẽ được cung cấp lương thực sản xuất ra từ tất cả các ô kề với khu dân cư này. Bạn có danh sách $k$ khu dân cư dự kiến sẽ xây dựng, trong đó khu dân cư thứ $i$ có nhu cầu tiêu thụ $c_i$ đơn vị lương thực mỗi tháng $(1 \le i \le k)$. Để tối ưu hóa quy hoạch, khu dân cư thứ $i$ có thể được xây dựng tại ô mà tổng lương thực sản xuất của các ô kề đúng bằng $c_i$.
Yêu cầu: Với mỗi khu dân cư, hãy cho biết tồn tại hay không trên bản đồ một vị trí để xây dựng đảm bảo yêu cầu nêu trên.
Dữ liệu: vào từ tập tin văn bản CITY.INP
- Dòng đầu tiên chứa 3 số nguyên dương $m$, $n$ và $k$ với $3 \le m, n \le 500$; $1 \le k \le 2000$.
- Dòng thứ $i$ trong số $m$ dòng tiếp theo chứa $n$ số tự nhiên lần lượt là số lương thực sản xuất được của các ô trên dòng $i$ của bản đồ.
- Dòng cuối cùng gồm $k$ số nguyên dương $c_1, c_2, \dots, c_k$ với $c_i$ là nhu cầu tiêu thụ lương thực của khu dân cư thứ $i$.
Kết quả: ghi ra tập tin văn bản CITY.OUT $k$ số tự nhiên 0 hoặc 1. Số thứ $i$ bằng 1 nếu có thể tìm được vị trí để xây dựng khu dân cư thứ $i$, trong trường hợp ngược lại số thứ $i$ bằng 0. Các số trên cùng một dòng cách nhau bởi đúng một ký tự khoảng trắng.
Giải thích ví dụ 1: khu dân cư 1 có thể xây được tại ô $(1, 1)$ (các ô kề có tổng $9 + 1 + 9 = 19$), khu dân cư 3 có thể xây được tại ô $(1, 2)$ (tổng $1 + 7 + 1 + 9 + 9 = 27$), còn hai khu dân cư 2 và 4 không có phương án xây.
Ghi chú của đề trên CLUE OJ: đề không nói rõ nhưng ta hiểu mỗi ô chỉ xây được 1 khu dân cư. Giả sử ví dụ trên là $k = 5$, có thêm 1 khu dân cư muốn xây với nhu cầu lại là 19, thì đáp án phải in ra 0, bởi vì chỉ có duy nhất 1 vị trí phù hợp có tổng lân cận bằng 19 và vị trí đó đã ưu tiên cho khu dân cư 1 (xét duyệt theo thứ tự từ trái qua phải). Tức là nếu có 5 khu dân cư cần xây là 19, 100, 27, 50, 19 thì đáp án là 1 0 1 0 0 (ví dụ 2).
Lưu ý: dữ liệu đọc ghi với file với tên file như trong đề bài (CITY.INP, CITY.OUT).
3 4 4
1 9 7 1
1 9 9 5
2 0 0 3
19 100 27 501 0 1 03 4 5
1 9 7 1
1 9 9 5
2 0 0 3
19 100 27 50 191 0 1 0 0Lời mở đầu
Bài này nằm ở cả 2 chương Mảng 2 chiều và Map/Set: phần mảng 2 chiều là tính tổng 8 ô xung quanh một ô, phần map là "đếm xem mỗi tổng xuất hiện bao nhiêu lần" để trả lời nhanh $k$ câu hỏi. Ngoài ra bộ test còn giấu một cái bẫy rất hiểm ở 5 test cuối mà mình sẽ chỉ ra bên dưới – nhiều bạn code đúng thuật toán mà vẫn mất điểm vì nó.
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 nhưng nhìn dữ liệu thì thấy rõ 3 nhóm:
| Test | Số test | $m \times n$ lớn nhất | $k$ lớn nhất | $a_{i,j}$ lớn nhất | Số $c_i$ dài hơn 9 chữ số | Số kết quả 1 |
|---|---|---|---|---|---|---|
| 1 – 10 | 10 | 5 × 5 | 20 | 128933 | 0 | 0 – 6 |
| 11 – 95 | 85 | 500 × 500 | 2000 | 132768 | 0 | 951 – 1053 |
| 96 – 100 | 5 | 500 × 500 | 2000 | 132768 | 381 – 415 số (dài tới 50 chữ số) | 787 – 839 |
- Test 1 – 10: lưới rất nhỏ (tối đa $5 \times 5$), $k \le 20$.
- Test 11 – 95: đều là lưới $500 \times 500$ với $k = 2000$ – lớn nhất theo đề. Giá trị $a_{i,j}$ thực tế chỉ tới khoảng $1{,}3 \cdot 10^5$, nên tổng 8 ô kề không vượt quá $8 \cdot 10^6$; khoảng một nửa số khu dân cư xây được.
- Test 96 – 100: giống nhóm 2 nhưng có khoảng 400 số $c_i$ dài từ 10 đến 50 chữ số! Đề chỉ nói $c_i$ là "số nguyên dương", không giới hạn trên. Số 50 chữ số thì
long long(tối đa khoảng $9{,}2 \cdot 10^{18}$, 19 chữ số) không chứa nổi.
Kết quả chạy thật của các cách giải bên dưới trên từng nhóm test (giới hạn 1 giây):
| Nhóm | Test | Đặc điểm | Cách 1 | Cách 2 | Cách 3 | Cách 3 đọc long long |
|---|---|---|---|---|---|---|
| Nhóm 1 | 1 – 10 | lưới nhỏ, $k \le 20$ | ✔ | ✔ | ✔ | ✔ |
| Nhóm 2 | 11 – 95 | $500 \times 500$, $k = 2000$ | ✘ đúng 0/85 còn lại TLE | ✔ | ✔ | ✔ |
| Nhóm 3 | 96 – 100 | như nhóm 2 + có $c_i$ hàng chục chữ số | ✘ đúng 0/5 còn lại TLE | ✔ | ✔ | ✘ đúng 0/5 còn lại WA |
Ý tưởngMỗi ô có một "con số" cố định
Gọi $S_{i,j}$ là tổng lương thực của các ô kề với ô $(i, j)$. Con số này chỉ phụ thuộc vào bản đồ, không phụ thuộc khu dân cư. Khu dân cư thứ $t$ xây được ở ô $(i, j)$ khi và chỉ khi ô đó còn trống và $S_{i,j} = c_t$.
Vì mỗi ô chỉ xây được 1 khu và các ô có cùng $S$ thì "như nhau", ta chỉ cần biết còn bao nhiêu ô trống có tổng bằng $c_t$: còn thì in 1 và bớt đi 1 ô, hết thì in 0. Xét các khu dân cư theo đúng thứ tự cho trong đề (ai đến trước được ưu tiên trước).
if kiểm tra ra ngoài.Em sửa bản đồ và danh sách $c$ rồi bấm Tiếp để xem từng bước: tính $S$ cho từng ô, đếm vào map, rồi lần lượt trả lời các khu dân cư:
Cách 1Mỗi khu dân cư, quét lại toàn bộ bản đồ
Cách tự nhiên nhất: với mỗi khu dân cư, duyệt mọi ô; ô nào còn trống thì tính tổng 8 ô kề bằng hàm tong8, bằng $c$ thì đánh dấu đã xây và dừng. Số $c$ mình đọc bằng xâu (lý do ở phần bẫy bên dưới), xâu dài hơn 9 chữ số thì gán $c = -1$ để chắc chắn không ô nào khớp.
- Điều kiện
!oktrong 2 vòng lặp giúp dừng ngay khi đã tìm được ô. - Mảng
akhai báo toàn cục cỡ $505 \times 505$ nên hàng 0, cột 0, hàng $m+1$, cột $n+1$ đều bằng 0 – chính là viền 0. - Khu dân cư không xây được sẽ phải quét hết $m \cdot n = 250\,000$ ô, mỗi ô 9 phép cộng; nhân với $k = 2000$ là khoảng $4{,}5 \cdot 10^9$ phép tính – quá chậm.
Kết quả chạy thật: đúng 10/100 test (sai 90 test: TLE), test đúng chậm nhất 0.00 giây. Chỉ qua được 10 test nhỏ. Python: bản Python đúng 10/100 test (các test lớn quá thời gian), test đúng chậm nhất 0.03 giây.
Cách 2Tính trước S một lần
Tổng 8 ô kề của một ô không đổi, vậy tính sẵn vào mảng S một lần duy nhất. Mỗi khu dân cư vẫn quét bản đồ nhưng mỗi ô chỉ còn 1 phép so sánh.
Dòng S[i][j] = -a[i][j] rồi cộng cả khối $3 \times 3$ chính là "cộng 9 ô, trừ ô giữa".
Kết quả chạy thật: đúng 100/100 test, test đúng chậm nhất 0.54 giây. Bất ngờ chưa: cách này vẫn qua hết! Khoảng một nửa số khu dân cư không xây được nên phải quét trọn $250\,000$ ô, tổng cộng cỡ $1000 \cdot 250\,000 = 2{,}5 \cdot 10^8$ phép so sánh – rất nhẹ nên chạy kịp, nhưng chỉ còn cách giới hạn 1 giây khoảng một nửa. Nếu $k$ lớn hơn (chẳng hạn $10^5$) thì cách này chắc chắn quá thời gian, nên mình vẫn muốn các bạn nắm cách 3.
Cách 3Đếm bằng map – trả lời mỗi khu dân cư trong O(log)
Thay vì quét bản đồ cho từng khu dân cư, ta gom các ô theo giá trị $S$: cnt[s] = số ô còn trống có tổng 8 ô kề bằng $s$. Khu dân cư cần $c$: nếu cnt[c] > 0 thì in 1 và giảm cnt[c] đi 1, ngược lại in 0. Vì $S$ có thể lên tới $8 \cdot 10^6$ và chỉ có $250\,000$ giá trị nên dùng map rất tiện (dùng mảng đếm cỡ $8 \cdot 10^6$ cũng được nếu tin chắc vào giới hạn $a_{i,j}$).
- Dùng
cnt.find(c)thay vìcnt[c]để không vô tình chèn thêm khoá mới vào map khi $c$ không tồn tại. - Nếu xâu $c$ dài hơn 9 chữ số thì $c \ge 10^9 > 8 \cdot 10^6$, chắc chắn in 0 mà không cần đổi sang số.
Kết quả chạy thật: đúng 100/100 test, test đúng chậm nhất 0.31 giây. Full điểm. Python: bản Python đúng 100/100 test, test đúng chậm nhất 0.42 giây.
BẫyĐọc c bằng long long thì sao?
Hầu hết các bạn sẽ viết tự nhiên như sau:
long long c;
cin >> c; // c có 50 chữ số thì sao?
auto it = cnt.find(c);
...Thuật toán y hệt cách 3, nhưng chạy thật trên bộ test thì: đúng 95/100 test (sai 5 test: WA), test đúng chậm nhất 0.30 giây. – sai đúng 5 test cuối 96 – 100, là các test có số $c_i$ khổng lồ.
Lý do: khi gặp một số 50 chữ số, cin >> c với long long bị tràn, C++ gán $c$ = giá trị lớn nhất của long long và bật cờ lỗi (failbit) cho cin. Từ lúc đó mọi lệnh cin phía sau đều bị bỏ qua và $c$ luôn bằng 0, nên toàn bộ các khu dân cư còn lại đều sai. Python thì không gặp chuyện này vì int của Python không giới hạn độ dài.
long long chỉ đạt 95/100. Thời gian đo bằng CPU time, giới hạn 1 giây. Bài đọc/ghi file CITY.INP/CITY.OUT: đoạn if(fopen(...)) giúp code vừa chạy được với file, vừa chạy được với bàn phím khi tự thử.
Nhận xét
Đăng nhận xét