Đường đi của Robot

Nguồn: CLUE OJ – Chương 22: Quy hoạch động (Tin học trẻ bảng B Đà Nẵng 2021–2022) Độ khó: Trung bình QHĐ trên lưới Số nguyên lớn

Đề bài

Có một lưới ô vuông 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 \times 3$ như hình vẽ sau:

Lưới 3x3, robot ở ô (1;1), đá ở ô (1;3) và (2;1)

Trong lưới ô vuông $3 \times 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 (file 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 < 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 (file ROBOT.OUT): ghi ra 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 < N \le 30$; 30% test ứng với $30 < N \le 100$.

Ví dụ – input

3 2
1 3
2 1

Ví dụ – output

Lưu ý: bài này đọc / ghi FILE

Trên CLUE OJ, dữ liệu đọc từ file với tên file như trong đề bài: ROBOT.INP và ROBOT.OUT. Code bên dưới dùng mẹo if(fopen("ROBOT.INP", "r")) { freopen(...); }: có file thì đọc ghi file, không có (khi các bạn tự chạy thử) thì đọc bàn phím.

Lời mở đầu

Đếm số đường đi trên lưới là bài QHĐ trên lưới "kinh điển nhất". Nhưng bài này có một cái bẫy rất hay ở subtask cuối: số đường đi lên tới gần $10^{59}$, nên lời giải QHĐ đúng mà dùng long long vẫn chỉ được 70% điểm. Mình sẽ đi qua 3 cách: quay lui đếm từng đường (30%), QHĐ với long long (70%), và QHĐ với phép cộng số lớn (100%).

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test3 subtask Ý tưởngTrên + trái Cách 1Quay lui 30%Cách 2long long 71%Cách 3Số lớn 100%

Bộ testBộ test chính thức có gì?

Test	$N$	$M$ (số viên đá)	Số chữ số của đáp án
1–30	2 – 10	1 – 7	1 – 5
31–70	11 – 30	1 – 25	5 – 17
71–100	34 – 100	1 – 73	19 – 59

Bộ test khớp đúng 3 subtask của đề: 30 test đầu $N \le 10$, 40 test tiếp $10 < N \le 30$, 30 test cuối $30 < N \le 100$. Không có test nào đặt đá ở ô $(1;1)$ hay ô $(N;N)$, không có viên đá trùng nhau. Điều quan trọng nhất là cột cuối: đáp án có tới 59 chữ số – vượt xa long long (chỉ chứa được khoảng 19 chữ số), nên subtask 3 bắt buộc phải tự cài cộng số lớn.

Subtask	Điều kiện	Test	Cách 1 quay lui	Cách 2 QHĐ long long	Cách 3 QHĐ số lớn
1 (30%)	$N \le 10$	1–30	qua	qua	qua
2 (40%)	$10 < N \le 30$	31–70	quá thời gian	qua	qua
3 (30%)	$30 < N \le 100$	71–100	quá thời gian	tràn số (chỉ đúng 1 test)	qua

Ý tưởngMuốn tới ô (i; j) thì bước cuối phải từ trên xuống hoặc từ trái sang

Robot chỉ đi sang phải hoặc xuống dưới, nên ô ngay trước ô $(i; j)$ trên đường đi chỉ có thể là ô phía trên $(i-1; j)$ hoặc ô bên trái $(i; j-1)$. Hai nhóm đường đi này không trùng nhau (bước cuối khác nhau), nên:

Công thức QHĐ

Gọi $f[i][j]$ = số đường đi từ $(1;1)$ tới ô $(i;j)$.

$f[1][1] = 1$ (đứng yên tại chỗ cũng là 1 cách).
Ô có đá: $f[i][j] = 0$ – không đường nào đi vào được.
Ô khác: $f[i][j]$ $= f[i-1][j] + f[i][j-1]$, các ô ngoài lưới (hàng 0, cột 0) coi như bằng 0.

Đáp án là $f[N][N]$.

Điền bảng theo từng hàng từ trên xuống, mỗi hàng từ trái sang phải: khi tới ô $(i;j)$ thì ô trên và ô trái chắc chắn đã có giá trị. Em nhập lưới rồi bấm Tiếp để xem từng ô được điền:

N Các ô có đá (hàng cột ...)

Ví dụ nhanh:

Cách 1Quay lui đi thử từng đường (subtask 1)

Cho robot "đi thật": từ ô hiện tại thử rẽ sang phải rồi thử đi xuống, gặp đá hoặc ra ngoài lưới thì quay lui, tới đích thì đếm thêm 1.

C++▶ Chạy tay từng dòng codeCách 1: quay lui – robot đi thử sang phải rồi xuống dưới, tới đích thì đếm.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Bước ở dòng if(i == n && j == n) gộp luôn dem++ và return.

Không gian$O(N)$ độ sâu đệ quy

Thời gian$O(\text{số đường đi} \cdot N)$

Mỗi lần tới đích chỉ cộng thêm 1 nên số bước ít nhất bằng chính đáp án. Với $N = 10$ đáp án tối đa $\binom{18}{9} = 48620$ – rất nhanh. Nhưng $N = 30$ đáp án cỡ $10^{16}$ thì có chạy cả năm cũng không xong.

Kết quả chạy thật: đúng 37/100 test: trọn 30 test subtask 1 (mỗi test dưới 0,01 giây) và thêm 7 test của subtask 2 có đáp án nhỏ (test 38, 39, 44, 55, 59, 65, 68 – đáp án chưa tới $2 \cdot 10^8$ vì có nhiều đá chặn). Các test còn lại có đáp án từ khoảng $1{,}4 \cdot 10^8$ trở lên đều quá thời gian (test 31 đáp án 139 triệu đã mất 1,1 giây). Bản Python cũng đúng 30/30 test của subtask 1 (chậm nhất 0,04 giây).

Cách 2QHĐ trên lưới với long long (subtask 1, 2)

Cài đặt đúng công thức ở phần ý tưởng. Mảng toàn cục nên hàng 0 và cột 0 tự động bằng 0, đóng vai trò "viền" ngoài lưới.

C++▶ Chạy tay từng dòng codeCách 2: điền bảng f theo hàng, f[i][j] = trên + trái (long long).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Thứ tự các if: kiểm tra đá trước, rồi mới tới ô xuất phát, cuối cùng là công thức cộng.
Với $N \le 30$, đáp án lớn nhất khoảng $\binom{58}{29} \approx 3 \cdot 10^{16}$ – vẫn vừa long long (tối đa $\approx 9{,}2 \cdot 10^{18}$).

Không gian$O(N^2)$

Thời gian$O(N^2)$

Kết quả chạy thật: đúng 71/100 test, mỗi test dưới 0,01 giây. Subtask 3 chỉ đúng được 1 test (test 87, $N = 34$, đáp án 19 chữ số còn vừa long long); 29 test còn lại sai vì tràn số – chương trình in ra những số vô nghĩa, có test còn in số âm.

Cách 3QHĐ + cộng số lớn bằng xâu (full điểm)

Công thức không đổi, chỉ đổi kiểu dữ liệu: mỗi ô lưu một xâu chữ số và ta tự viết hàm cộng 2 số lớn theo cách cộng tay hồi tiểu học – cộng từ hàng đơn vị (cuối xâu), nhớ sang hàng tiếp theo.

Em thử phép cộng số lớn ở đây (bấm Tiếp để cộng từng cột):

a b

Ví dụ nhanh:

C++▶ Chạy tay từng dòng codeCách 3: bảng f lưu xâu chữ số, cộng bằng hàm cong (cộng tay từng cột).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Trong hàm cong, vòng while chạy tới khi cả hai số hết chữ số và không còn nhớ – thiếu điều kiện nho > 0 là sẽ mất chữ số 1 đầu tiên khi cộng kiểu $99 + 1$.
Ta nối chữ số vào cuối xâu c (nhanh), tức là đang viết ngược; cuối cùng reverse lại một lần.
Phải khởi tạo mọi ô bằng "0" (kể cả hàng 0, cột 0), vì string rỗng không phải là số 0 hợp lệ khi in ra.

Không gian$O(N^2 \cdot K)$, $K \approx 60$ chữ số

Thời gian$O(N^2 \cdot K)$

Với $N = 100$ có $10^4$ ô, mỗi phép cộng tối đa khoảng 60 chữ số → chỉ cỡ $6 \cdot 10^5$ phép tính.

Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,007 giây. Bản Python còn khoẻ hơn: số nguyên của Python không bao giờ tràn, chỉ cần viết đúng công thức – đúng 100/100, chậm nhất 0,02 giây.

Ghi chú của mình: 100 test chia đúng 3 subtask của đề. Quay lui chỉ qua subtask 1 (30/100), QHĐ long long được 71/100 (sai vì tràn số ở subtask 3), QHĐ cộng số lớn được 100/100 (≤ 0,007 s). Python với số nguyên tự do cũng 100/100. Nhớ đọc ghi file ROBOT.INP/ROBOT.OUT khi nộp.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Lập Trình Thuật Toán