Đường Đi Của Robot (ROBOT)
Đề bài
Bài 4. Đường đi của Robot (2.0 điểm) – Hội thi Tin học trẻ cấp thành phố Đà Nẵng, năm học 2021–2022, đề thi Bảng B – cấp THCS.
Có một lưới ô vuông có kích thước $N \times N$ được đánh chỉ số hàng từ 1 đến $N$ (theo chiều từ trên xuống dưới) và chỉ số cột từ 1 đến $N$ (theo chiều từ trái sang phải). Mỗi ô trong lưới được xác định vị trí bởi một cặp số $(i; j)$ trong đó $i$ là chỉ số hàng và $j$ là chỉ số cột.
Tại ô $(1; 1)$ người ta đặt một con robot tự hành. Mỗi lần di chuyển robot chỉ đi sang phải một ô hoặc đi xuống dưới một ô. Trong lưới ô vuông này người ta đặt một viên đá vào một số ô để làm vật cản.
Yêu cầu: Hãy tính xem có bao nhiêu đường đi từ ô $(1; 1)$ đến ô $(N; N)$. Biết rằng robot không thể đi vào ô có vật cản và hai đường đi được gọi là khác nhau nếu có ít nhất một ô thuộc đường đi này nhưng không thuộc đường đi kia.
Ví dụ: Xét lưới ô vuông kích thước 3×3 như hình vẽ sau:
Trong lưới ô vuông 3×3 này người ta đặt viên đá vào ô $(1;3)$ và ô $(2;1)$. Với dữ kiện trên thì robot có tất cả 2 đường đi như sau:
- $(1;1) \to (1;2) \to (2;2) \to (2;3) \to (3;3)$
- $(1;1) \to (1;2) \to (2;2) \to (3;2) \to (3;3)$
Input: Đọc từ file văn bản ROBOT.INP có cấu trúc như sau:
- Dòng đầu tiên chứa 2 số nguyên dương $N$ và $M$ (mỗi số cách nhau 1 dấu cách; $M \lt N$).
- $M$ dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương $i$ và $j$ (mỗi số cách nhau một dấu cách) là chỉ số hàng và chỉ số cột của ô được đặt vào đó một viên đá là vật cản.
Output: Ghi ra file văn bản ROBOT.OUT một số $k$ là số đường đi của robot từ ô $(1; 1)$ đến ô $(N; N)$.
Giới hạn: 30% test ứng với $N \le 10$; 40% test ứng với $10 \lt N \le 30$; 30% test ứng với $30 \lt N \le 100$.
(Thời gian làm bài cả đề: 150 phút. Trên hệ thống chấm online thì đọc dữ liệu từ bàn phím và ghi ra màn hình – đọc/ghi chuẩn – nên trong code mình để sẵn 2 dòng freopen dưới dạng chú thích, khi thi offline thì bỏ // đi.)
3 2
1 3
2 12Lời mở đầu
Bài này là bài 4 trong đề Tin học trẻ cấp thành phố Đà Nẵng, một bài quy hoạch động trên lưới rất kinh điển. Nhưng đừng thấy kinh điển mà chủ quan nha các bạn, bài này có một cái bẫy "chết người" mà rất nhiều bạn dính – mình sẽ cho các bạn xem tận mắt luôn 😉.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJGiải thích ví dụ cho bạn nào chưa hiểu đề: lưới 3×3, đá ở $(1;3)$ và $(2;1)$. Từ $(1;1)$ robot không đi xuống được (vì $(2;1)$ có đá) nên bắt buộc sang phải tới $(1;2)$. Từ $(1;2)$ không sang phải được (vì $(1;3)$ có đá) nên bắt buộc xuống $(2;2)$. Từ $(2;2)$ thì có 2 lựa chọn: sang phải $(2;3)$ rồi xuống $(3;3)$, hoặc xuống $(3;2)$ rồi sang phải $(3;3)$. Vậy có đúng 2 đường đi.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Quy hoạch động trên lưới – O(N²)
Bài này giải theo phương pháp Quy Hoạch Động (Dynamic Programming) nha các bạn. Cho bạn nào đã biết cơ bản về quy hoạch động thì mình đi theo 4 bước quen thuộc:
- Xác định bài toán con: gọi $F[i][j]$ là số đường đi khác nhau từ ô đầu tiên $(1, 1)$ đến ô $(i, j)$.
- Bài toán cơ sở: $F[1][1] = 1$ vì luôn có đúng một đường đi từ ô bắt đầu đến chính nó. Tại những ô có đá thì $F = 0$, vì không thể nào đi vào đó được.
- Đáp án: quá rõ ràng, đó chính là $F[N][N]$ – số đường đi khác nhau để đến ô đích $(N, N)$.
- Công thức truy hồi: robot chỉ đi sang phải hoặc đi xuống. Xét ngược lại tại ô $(i, j)$: ngay bước trước đó robot chỉ có thể đang đứng ở ô bên trái $(i, j-1)$ hoặc ô bên trên $(i-1, j)$. Vậy số cách đi đến $(i, j)$ bằng tổng số cách đi đến hai ô đó.
Cần lưu ý khi $i = 1$ thì phía trên không có ô nào, khi $j = 1$ thì bên trái cũng không có ô nào. Chỗ này xét thêm điều kiện cũng được nhưng code sẽ dài dòng. Cách gọn nhất: khai báo mảng $F$ có $N+1$ dòng, $N+1$ cột và cho toàn bộ dòng 0, cột 0 mang giá trị 0. Khi xét $i = 1$ hay $j = 1$ mà có gọi tới dòng 0, cột 0 thì cộng thêm 0 cũng chẳng làm thay đổi gì.
Em nhập kích thước lưới và vị trí các viên đá, rồi bấm Tiếp để xem bảng $F$ được tô từng ô (xanh tím = 2 ô "nguồn" bên trái và bên trên, ô đen = đá):
Lưu ý: việc tính $F[i][j]$ ở trên chỉ áp dụng cho những ô đi vào được; ô có đá thì mặc định là 0, không cần tính. Nghĩa là phải có điều kiện "$F[i][j]$ khác 0 thì mới tính và cập nhật".
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
// freopen("ROBOT.INP", "r", stdin);
// freopen("ROBOT.OUT", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
long long f[n + 1][n + 1];
for(int i = 0; i <= n; ++i){
for(int j = 0; j <= n; ++j){
if(i == 0 || j == 0){
f[i][j] = 0;
}
else{
f[i][j] = -1;
}
}
}
while(m--){
int x, y;
cin >> x >> y;
f[x][y] = 0;
}
f[1][0] = 1;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(f[i][j] != 0){
f[i][j] = f[i][j - 1] + f[i - 1][j];
}
}
}
cout << f[n][n];
return 0;
}import sys
# sys.stdin = open("ROBOT.INP", "r")
# sys.stdout = open("ROBOT.OUT", "w")
n, m, *rest = map(int, sys.stdin.read().split())
f = [[0 if i == 0 or j == 0 else -1 for j in range(n + 1)] for i in range(n + 1)]
index = 0
while m > 0:
x = rest[index]
y = rest[index + 1]
f[x][y] = 0
index += 2
m -= 1
f[1][0] = 1
for i in range(1, n + 1):
for j in range(1, n + 1):
if f[i][j] != 0:
f[i][j] = f[i][j - 1] + f[i - 1][j]
print(f[n][n])Giải thích một số chỗ trong code:
1/ Hai dòng ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); giúp đẩy nhanh tốc độ nhập xuất khi code C++ (các bạn gõ mấy từ này lên Google sẽ ra rất nhiều bài giải thích nhé). Kinh nghiệm: bài nào nhập xuất nhiều thì nên thêm vào đầu hàm main.
2/ Ở 2 vòng lặp lồng nhau đầu tiên: với $i = 0$ hay $j = 0$ thì gán $F[i][j] = 0$ như đã nói ở bước 4, còn các ô còn lại mình gán $-1$. Tại sao? Vì ở bước xử lý mình chỉ tính khi $F[i][j] \ne 0$. Nếu không gán sẵn một giá trị khác 0, tùy compiler mà các ô chưa gán có thể mang giá trị rác hoặc vô tình bằng 0 – lỡ ô đó không có đá mà lại bằng 0 thì sẽ bị bỏ qua không tính ⇒ sai. Gán $-1$ cho chắc: ô nào $\ne 0$ là ô cần tính, ô $= 0$ chắc chắn là đá.
3/ Dòng f[1][0] = 1; mà bỏ đi là sai nhé các bạn! Theo bước 2 thì $F[1][1] = 1$, nhưng nếu gán thẳng $F[1][1] = 1$ thì vào vòng lặp nó lại thấy $F[1][1] \ne 0$ và tính lại $F[1][1] = F[0][1] + F[1][0] = 0 + 0 = 0$ ⇒ sai. Muốn né thì phải thêm điều kiện kiểu i != 1 || j != 1, dài dòng mà còn phải so sánh thêm ở mọi ô. Gọn nhất là cho $F[1][0] = 1$: khi tính $F[1][1] = F[0][1] + F[1][0] = 0 + 1 = 1$ đúng mục tiêu, và $F[1][0]$ chỉ ảnh hưởng đúng ô $F[1][1]$ chứ không ảnh hưởng ô nào khác. Các bạn cũng có thể cho $F[0][1] = 1$ thay vào, nhưng chỉ một trong hai thôi nha, cho cả hai bằng 1 là sai đấy.
Khung chạy tay dưới đây chạy đúng code C++ ở trên, em bấm Tiếp để xem từng dòng nhé:
Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng 2 chiều $F$ ⇒ $O(N^2)$ (ở đây $N^2$ là $N$ lũy thừa 2 nha, không phải phép xor bit).
- Thời gian: khởi tạo mảng $O(N^2)$, đọc các viên đá $O(M)$, bước xử lý chính $O(N^2)$. Mà chắc chắn $M \le N^2$ (nhiều nhất thì mọi ô đều có đá; đề còn cho $M \lt N$). Theo quy tắc cộng Big-O thì lấy thành phần lớn nhất ⇒ $O(N^2)$.
Với $N \le 100$ thì $N^2 = 10^4$, nhỏ hơn rất nhiều so với ngưỡng khoảng $10^8$ phép tính trong 1 giây, nên yên tâm không sợ TLE.
Thực tế khi mình nộp thì code C++ ở trên bị WA 28 test, còn code Python thì AC. Đây là một test bị sai:
42 1
2 27424784580527499807432510unsigned long long) cũng chỉ khoảng $1.8 \cdot 10^{19}$ – tức 20 chữ số. Bị tràn số là đúng rồi. Python thì tự xử lý được số lớn nên không bị lỗi.Bạn nào kỹ tính có thể đoán trước việc tràn số này bằng cách tự đặt tình huống: không có viên đá nào. Khi đó các bạn mở Excel làm nháp các bảng từ 1×1 đến 5×5 sẽ thấy: tại các ô trên đường chéo chính $(1,1), (2,2), \dots, (N,N)$, hai ô bên trái và bên trên luôn có giá trị bằng nhau, nên ô chéo $\ge$ gấp đôi hai ô đó. Cứ mỗi bước xuống một ô chéo mới là giá trị tăng gấp đôi trở lên. Số nguyên 8 byte có 64 bit, tức là nhân 2 tối đa khoảng 64 lần là tràn; trong khi lưới tới $100 \times 100$ – nội việc này thôi đã đủ thấy chắc chắn tràn rồi, chưa kể thực tế còn tăng nhanh hơn gấp đôi nữa.
Mình chạy thử code C++ ở trên với lưới không có đá để các bạn thấy nó "gãy" ở đâu:
| Input | Đáp án đúng | Code long long in ra |
|---|---|---|
| 34 0 | 7219428434016265740 | 7219428434016265740 |
| 35 0 | 28453041475240576740 | -8440446672178526492 |
| 42 1 / 2 27 | 424784580527499807432510 | 4631081169483718960 |
| 100 0 | 22750883079422934966181954039568885395604168260154104734000 | (số rác) |
Tức là chỉ cần lưới cỡ $35 \times 35$ không có đá là long long đã tràn, ra cả số âm luôn 😱. Với subtask $N \le 30$ thì vẫn an toàn (lưới trống $30 \times 30$ cho đáp án khoảng $3 \cdot 10^{16}$), nên cách 1 chỉ chắc ăn khoảng 70% test.
Cách 2Quy hoạch động + cộng số lớn bằng chuỗi – O(N² · L)
Vậy chỗ này phải xử lý tràn số, tức là quy về bài toán số lớn (BigInt). Bạn nào dùng ngôn ngữ có hỗ trợ sẵn số lớn như C#, Java, Python… thì chỉ cần gọi ra dùng, đơn giản lắm. Nhưng nếu chỉ biết mỗi C++ thì phải tự cài đặt. Không cần cài hết các phép toán đâu nha: bài này chỉ cần phép cộng 2 số lớn để tính $F[i][j] = F[i][j-1] + F[i-1][j]$. Hơn nữa toàn là số không âm nên không phải lo trường hợp số âm (có số âm thì phải làm thêm cả phép trừ).
Quy tắc xử lý số lớn: dùng chuỗi để lưu các chữ số – số dài cả triệu chữ số thì chuỗi vẫn lưu được. Còn cách cộng thì y hệt phép cộng hồi tiểu học: đi từ hàng đơn vị của 2 số, cộng 2 chữ số lại (cộng thêm phần nhớ nếu có); nếu vượt quá 9 thì viết chữ số hàng đơn vị và nhớ phần hàng chục (ví dụ 15 thì viết 5 nhớ 1). Số nào hết chữ số trước thì số còn lại cứ "hạ" tiếp xuống, cộng với nhớ. Cuối cùng nếu còn nhớ thì viết thêm vào. Kết quả ghi theo thứ tự từ phải qua trái.
- 7 + 5 = 12 > 9 ⇒ viết 2 nhớ 1 ⇒ "2".
- 6 + 4 + 1 (nhớ) = 11 ⇒ viết 1 nhớ 1 ⇒ "12".
- Số thứ 2 hết; hạ 1 của số đầu, cộng nhớ: 1 + 1 = 2 ⇒ "212".
- 9 + 1 = 10 ⇒ viết 0 nhớ 1 ⇒ "0".
- 9 + 2 + 1 = 12 ⇒ viết 2 nhớ 1 ⇒ "20".
- Hạ 9, cộng nhớ: 9 + 1 = 10 ⇒ viết 0 nhớ 1 ⇒ "020".
- Hết chữ số, còn nhớ 1 ⇒ viết luôn ⇒ "1020".
Em nhập 2 số rồi bấm Tiếp để xem từng cột được cộng như thế nào:
Đây là hàm cộng 2 số lớn của mình:
string Add(const string &a, const string &b){
string res;
int i = a.length() - 1, j = b.length() - 1;
int digit = 0;
while(i >= 0 || j >= 0){
int x = digit;
if(i >= 0){
x += a[i] - 48;
i--;
}
if(j >= 0){
x += b[j] - 48;
j--;
}
digit = x / 10;
x %= 10;
res.push_back(x + 48);
}
if(digit != 0){
res.push_back(digit + 48);
}
reverse(res.begin(), res.end());
return res;
}Giải thích một số chỗ trong hàm Add:
1/ Tham số là const string &a, const string &b thay vì string a, string b. Truyền kiểu tham trị (string a) thì compiler phải tạo bản sao – chuỗi dài 1 triệu ký tự là phải chép 1 triệu ký tự, tốn công lắm. Dấu & (tham chiếu) giúp làm việc thẳng trên vùng nhớ của biến gốc, khỏi sao chép. Còn const đặt trước để đề phòng lỡ tay sửa chuỗi trong hàm (sửa là sửa luôn biến gốc!) – có const thì compiler báo lỗi ngay. Nên const string &a là một cụm đi kèm nhau nha các bạn.
2/ Biến i duyệt chuỗi a từ chỉ số cuối (a.length() - 1, tức hàng đơn vị), j tương tự cho b; digit là biến nhớ, ban đầu bằng 0. Vòng lặp chạy khi còn ít nhất một chuỗi chưa duyệt hết (i >= 0 || j >= 0); chuỗi nào đã hết thì chỉ số thành $-1$ và if tương ứng không chạy nữa – đó chính là bước "hạ" chữ số của chuỗi còn lại. Ký tự số phải - 48 để đổi sang số (mã ASCII của '0' là 48, '1' là 49…). Sau khi cộng: digit = x / 10 lấy phần nhớ (x ≤ 9 thì nhớ 0; x = 15 thì nhớ 1), x %= 10 giữ chữ số hàng đơn vị, rồi + 48 đổi lại thành ký tự và đưa vào cuối res.
3/ Hết vòng lặp, nếu digit vẫn khác 0 thì ghi thêm vào. Vì nãy giờ ta ghi chữ số hàng đơn vị trước (từ trái sang phải trong res), mà số thì phải đọc từ hàng cao nhất, nên cuối cùng reverse đảo ngược cả chuỗi rồi trả về.
Add đúng, các bạn viết một chương trình random 2 số a, b trong phạm vi long long (cỡ $10^{17}$ để tổng không tràn), so to_string(a + b) với Add(to_string(a), to_string(b)), treo máy 5–10 phút; có trường hợp nào khác nhau thì in ra FAIL kèm dữ liệu để soi. Mọi thứ vẫn OK thì yên tâm.Giờ chỉ cần ráp hàm Add vào chương trình ban đầu: đổi kiểu mảng $F$ từ long long sang string, những chỗ gán 0 hay $-1$ thì bọc trong dấu nháy kép ("0", "-1"), và chỗ tính thì gọi Add. Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
string Add(const string &a, const string &b){
string res;
int i = a.length() - 1, j = b.length() - 1;
int digit = 0;
while(i >= 0 || j >= 0){
int x = digit;
if(i >= 0){
x += a[i] - 48;
i--;
}
if(j >= 0){
x += b[j] - 48;
j--;
}
digit = x / 10;
x %= 10;
res.push_back(x + 48);
}
if(digit != 0){
res.push_back(digit + 48);
}
reverse(res.begin(), res.end());
return res;
}
int main(){
// freopen("ROBOT.INP", "r", stdin);
// freopen("ROBOT.OUT", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
string f[n + 1][n + 1];
for(int i = 0; i <= n; ++i){
for(int j = 0; j <= n; ++j){
if(i == 0 || j == 0){
f[i][j] = "0";
}
else{
f[i][j] = "-1";
}
}
}
while(m--){
int x, y;
cin >> x >> y;
f[x][y] = "0";
}
f[1][0] = "1";
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(f[i][j] != "0"){
f[i][j] = Add(f[i][j - 1], f[i - 1][j]);
}
}
}
cout << f[n][n];
return 0;
}import sys
# sys.stdin = open("ROBOT.INP", "r")
# sys.stdout = open("ROBOT.OUT", "w")
def Add(a, b):
res = []
i, j = len(a) - 1, len(b) - 1
digit = 0
while i >= 0 or j >= 0:
x = digit
if i >= 0:
x += ord(a[i]) - 48
i -= 1
if j >= 0:
x += ord(b[j]) - 48
j -= 1
digit = x // 10
x %= 10
res.append(chr(x + 48))
if digit != 0:
res.append(chr(digit + 48))
return ''.join(reversed(res))
n, m, *rest = map(int, sys.stdin.read().split())
f = [["0" if i == 0 or j == 0 else "-1" for j in range(n + 1)] for i in range(n + 1)]
index = 0
while m > 0:
x = rest[index]
y = rest[index + 1]
f[x][y] = "0"
index += 2
m -= 1
f[1][0] = "1"
for i in range(1, n + 1):
for j in range(1, n + 1):
if f[i][j] != "0":
f[i][j] = Add(f[i][j - 1], f[i - 1][j])
print(f[n][n])Add) để các bạn đối chiếu. Thực ra với Python thì code của Cách 1 đã AC rồi, vì số nguyên của Python tự lớn bao nhiêu cũng được.Khung chạy tay cho code C++ cách 2 – lần này em sẽ thấy cả từng bước bên trong hàm Add:
Đánh giá độ phức tạp của cách làm này: các bạn chạy thử chương trình với input 100 0 (lưới $100 \times 100$ không có đá) sẽ được $F[100][100]$ bằng 22750883079422934966181954039568885395604168260154104734000 – có tới 59 chữ số. Gọi $L$ là số chữ số lớn nhất ($L \le 59$):
- Không gian: $N^2$ chuỗi, mỗi chuỗi tối đa $L$ ký tự ⇒ $O(N^2 \cdot L)$.
- Thời gian: mỗi ô gọi
Addmột lần, mỗi lần duyệt hết chuỗi ⇒ $O(N^2 \cdot L)$. Với bài này $L \le 59$ có thể xem như hằng số nên vẫn có thể nói gọn là $O(N^2)$ – cỡ $10^4 \times 59 \approx 6 \cdot 10^5$ phép tính, quá nhẹ.
Với source code này thì sẽ được Accepted nha các bạn 🎉.
long long.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét