Mario Nhảy Cột
Đề bài
MARIO là một trò chơi rất quen thuộc với các bạn trẻ. Trong trò chơi, muốn kết thúc một cửa chơi, MARIO phải nhảy để kéo một lá cờ từ đỉnh xuống dưới chân cột cờ.
Trong phiên bản mới, MARIO đang ở bờ bên trái sông còn cột cờ được đặt tại bờ bên phải sông, trên sông có $N$ chiếc cọc gỗ để giúp MARIO sang sông. MARIO có thể nhảy di chuyển từ cọc $i$ bước sang cọc $i + 1$, hoặc nhảy sang cọc $i + 2$ hoặc nhảy sang cọc $i + 3$. Tuy nhiên, người thiết kế trò chơi có làm khó người chơi bằng cách thiết kế một vài chiếc cọc lung lay, vài chiếc cọc khác lại bị mục nát.
- Với một chiếc cọc $i$ lung lay: MARIO chỉ có thể bước từ cọc $i - 1$ tới cọc $i$, và từ cọc $i$ chỉ có thể bước sang cọc $i + 1$ hoặc nhảy sang cọc $i + 2$.
- Với một chiếc cọc bị mục nát: MARIO không thể đứng trên đó vì nó sẽ gãy và MARIO sẽ bị rơi xuống sông.
- MARIO chỉ có thể đi tiến lên phía trước chứ không thể lùi lại khi đi trên cọc để qua sông.
Cu Tý nhà ta đã rất nhiều lần qua được sông, vì cậu là một game thủ siêu hạng. Tuy nhiên, lần này cậu lại nảy sinh ý nghĩ là phải qua sông theo một cách thật độc đáo để cho đám bạn phải thán phục, vì vậy cậu muốn biết có bao nhiêu cách để qua được sông, từ đó mới chọn ra cách độc đáo nhất. Bạn hãy lập trình, trả lời câu hỏi giúp Cu Tý.
Dữ liệu nhập:
- Dòng 1: chứa số nguyên dương $N$ $(1 \le N \le 1000)$.
- Dòng 2: chứa $N$ số nguyên $A_1, A_2, \ldots, A_N$, với $A_i \in \{0, 1, 2\}$. Trong đó:
- $A_i = 0$: nếu cọc $i$ là cọc tốt;
- $A_i = 1$: nếu cọc $i$ là cọc lung lay;
- $A_i = 2$: nếu cọc $i$ là cọc bị mục.
Kết quả: là số lượng cách đi để có thể qua sông. Do số lượng này rất lớn nên chỉ cần in ra 9 chữ số cuối (mod $10^9$).
Lưu ý: bờ trái và bờ phải có chức năng tương tự như cọc tốt.
Giới hạn: thời gian 1 giây, bộ nhớ 128 MB.
4
0 1 2 025
0 0 2 1 20Giải thích:
- Ví dụ 1: MARIO sẽ có 2 cách đi như sau:
- Cách 1: từ bờ bên trái bước đến cọc 1, từ cọc 1 nhảy đến cọc 4, từ cọc 4 bước sang bờ bên phải.
- Cách 2: từ bờ bên trái bước đến cọc 1, từ cọc 1 bước sang cọc 2, từ cọc 2 nhảy sang cọc 4, từ cọc 4 bước sang bờ bên phải.
- Ví dụ 2: MARIO không thể qua sông vì: từ bờ có thể đến cọc 1, cọc 2:
- Từ cọc 1, không thể sang cọc 3 (vì cọc 3 mục), không thể sang cọc 4 (vì cọc 4 lung lay nên chỉ có thể bước từ cọc 3 sang).
- Từ cọc 2, không thể sang cọc 3 (vì cọc 3 mục), không thể sang cọc 4 (vì cọc 4 lung lay nên chỉ có thể bước từ cọc 3 sang), không thể sang cọc 5 (vì cọc 5 mục).
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạ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é:
Link này công khai, bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên NTUCoderTrước tiên mình sẽ tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu như sau: Mario cần đi từ bờ bên này sang bờ bên kia. Bờ bên này có số thứ tự là $0$, bờ bên kia có số thứ tự là $n + 1$, ở giữa 2 bờ có 1 con sông có $n$ cái cọc $(1 \le n \le 1000)$ để Mario nhảy lên qua sông. Có 3 loại cọc trên sông:
- Cọc tốt ($a[i] = 0$): Mario có thể nhảy từ cọc $i - 3$ hoặc $i - 2$ hoặc $i - 1$ đến cọc $i$, và từ cọc $i$ có thể nhảy tới cọc $i + 1$ hoặc $i + 2$ hoặc $i + 3$.
- Cọc lung lay ($a[i] = 1$): Mario chỉ có thể nhảy từ cọc $i - 1$ tới cọc $i$, và từ cọc $i$ chỉ có thể nhảy tới cọc $i + 1$ hoặc $i + 2$.
- Cọc mục nát ($a[i] = 2$): Mario không thể đứng được, nói cách khác nếu Mario nhảy lên cọc này thì Mario sẽ bị rớt xuống sông.
Mario chỉ có thể đi tiến lên phía trước chứ không thể đi lùi. Hãy in ra số lượng cách đi để có thể qua sông chia dư cho $10^9$. Lưu ý là hai bên bờ cũng được tính như một cọc tốt, nói cách khác $a[0] = a[n + 1] = 0$.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn bằng đệ quy – đi ngược từ bờ phải
Cách làm đầu tiên của bài này sẽ là vét cạn nha, tức là ta sẽ thử mọi trường hợp đó. Cách làm này sẽ dùng tới đệ quy và sẽ khá là phức tạp cho bạn nào chưa quen với đệ quy, nhưng nó là cách dễ nghĩ tới nhất vì ý tưởng của nó là thử mọi trường hợp có thể xảy ra mà. Giờ mình sẽ phân tích rồi cài đặt để hi vọng các bạn sẽ học được thêm điều gì đó.
Đi xuôi hay đi ngược?
Ý tưởng của việc thử hết tất cả trường hợp sẽ là từ 1 cọc ta có thể đi tới những cọc nào hoặc là có những cọc nào có thể đi tới cọc ta đang xét. Thì ở đây ta sẽ lựa cái nào thuận tiện nhất để cài đặt thôi.
Nếu ta mà chọn "từ 1 cọc ta có thể đi tới những cọc nào" thì đầu tiên ta phải xét cọc đang xét là cọc loại gì, nó nhảy tới được cọc nào, cọc nó nhảy tới mà là cọc lung lay thì nó có nhảy được không (vì giả dụ giờ cọc ta đang xét là cọc $i$, mà cọc $i + 2$ là cọc lung lay thì làm sao nhảy tới được). Cũng khá là phức tạp. Vậy nên theo mình thì chúng ta sẽ nên làm theo cách có những cọc nào có thể đi tới cọc ta đang xét.
Tổng quát thì giờ giả sử ta đang xét cọc $i$:
- Nếu $a[i] = 0$ (cọc tốt) thì để nhảy tới cọc $i$ có thể là từ cọc $i - 1$ hoặc $i - 2$, vì dù cọc trước đó có lung lay hay tốt thì ta đều có thể nhảy xa 1 đến 2 cọc; còn nếu tới từ cọc $i - 3$ thì phải check là $a[i - 3] = 0$ vì chỉ có cọc tốt mới nhảy được 3 bước.
- Nếu $a[i] = 1$ (cọc lung lay) thì chỉ có thể nhảy từ cọc $i - 1$ tới thôi.
- Nếu $a[i] = 2$ (cọc mục nát) thì sẽ không tới từ cọc nào cả vì cọc bị hỏng mà, nhảy vô để rớt xuống sông à 😂.
Ta sẽ bắt đầu xét từ bờ bên phải, tức từ $n + 1$, rồi xét cứ dần về bờ bên trái; nếu có lúc $i = 0$, tức là có đường để từ bờ bên trái qua bờ bên phải thì ta tăng biến đếm cnt lên thôi. (Còn cọc mục ở vị trí $i - 1$, $i - 2$ thì cũng không sao: khi gọi tới nó, nó rơi vào trường hợp $a = 2$ và tự dừng.)
Hàm Try(i)
Giờ ta sẽ gọi hàm Try(int i) sẽ giúp ta thử mọi trường hợp đến cọc $i$:
- Nếu $i = 0$, ta sẽ tăng biến đếm.
- Nếu $i > 0$ (ta phải check nhé, không thì nhỡ $i$ âm cái là lỗi chương trình đó), thì ta sẽ xét: nếu $a[i] = 0$ thì ta sẽ gọi
Try(i - 1)rồiTry(i - 2), rồi ta sẽ check(i - 3 >= 0 && a[i - 3] == 0), nếu có thì ta mới gọiTry(i - 3). Ta cần check $i - 3 \ge 0$ để đảm bảoa[i - 3]không bị lỗi truy cập, và $a[i - 3] = 0$ tức là cọc tốt thì mới nhảy tới $i$ được. - Nếu mà $a[i] = 1$ thì ta chỉ việc
Try(i - 1)vì để tới cọc lung lay thứ $i$ thì chỉ có thể nhảy từ cọc $i - 1$ mà. - Trường hợp còn lại là $a[i] = 2$ tức là cọc mục nát thì ta kệ thôi, không gọi đệ quy nữa.
Đây là source code cho bạn nào muốn tham khảo cách làm trên của mình nha:
Code vét cạn (TLE từ test 5)
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (ll)1e9;
int n;
int a[1005];
ll cnt = 0;
void Try(int i){
if(i == 0){
cnt++;
cnt %= mod;
}
else if(i > 0){
if(a[i] == 0){
Try(i - 1);
Try(i - 2);
if(i - 3 >= 0 && a[i - 3] == 0){
Try(i - 3);
}
}
else if(a[i] == 1){
Try(i - 1);
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
a[0] = a[n + 1] = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
Try(n + 1);
cout << cnt;
return 0;
}import sys
sys.setrecursionlimit(2000) # Tránh lỗi đệ quy sâu
MOD = int(1e9)
cnt = 0
def Try(i):
global cnt
if i == 0:
cnt += 1
cnt %= MOD
elif i > 0:
if a[i] == 0:
Try(i - 1)
Try(i - 2)
if i - 3 >= 0 and a[i - 3] == 0:
Try(i - 3)
elif a[i] == 1:
Try(i - 1)
n = int(input())
a = [0] + list(map(int, input().split())) + [0]
Try(n + 1)
print(cnt)Giải thích 1 số chỗ trong cách làm trên:
ios_base::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé). Kinh nghiệm là bài nào dữ liệu đầu vào nhiều, như bài này có thể lên đến $10^3$ số, thì ta nên để 2 dòng này vào để chạy nhanh hơn.cnt %= mod: ở đây ta đang áp dụng đồng dư thức về phép cộng nha các bạn, dành cho bạn nào chưa biết thì $(a + b) \bmod m$ $= ((a \bmod m) + (b \bmod m)) \bmod m$. Nên thay vì ta cộng xongcntrồi mới chia dư thìcntnó sẽ rất to, ta sẽ chia dư ở mỗi lần cộng luôn.a[0] = a[n + 1] = 0: vì hai bên bờ được coi như là cọc tốt mà, nên ta cho luôn bằng 0.Try(n + 1): ta đang thử mọi trường hợp để đến được bờ bên phải thì ta sẽ phải bắt đầu từ bờ bên phải.
Đánh giá độ phức tạp của cách làm trên:
Thời gian thực sự tính chính xác thì mình cũng khó chính xác được cho các bạn. Nhưng chắc chắn cách này sẽ bị TLE, vì các bạn cứ thử nhập $N = 40$ và toàn là số 0 thì cách trên phải chờ rất lâu mới ra kết quả, trong khi đó đề bài đang yêu cầu phải ra kết quả trong 1 giây. Mà chỉ mới là $N = 40$ thôi mà còn chờ lâu như thế trong khi đề bài cho $N$ tối đa 1000 thì còn lâu cỡ nào nữa. Thực tế nộp cách này lên web thì chỉ vượt qua được 4 test và tại test 5 bị TLE (tổng cộng có 24 test).
Vậy cách trên không thể AC được rồi, tuy nhiên hãy vẫn nên cài đặt nó để sau này ta lấy nó làm công cụ kiểm tra tính chính xác cho cách làm tối ưu.
Cách 2Quy hoạch động – 4 bước
Để mà có thể AC được bài này thì ta sẽ dùng phương pháp Quy Hoạch Động (Dynamic Programming) để giải quyết nha các bạn. Nhìn lại cách vét cạn: Try(i) bị gọi đi gọi lại rất nhiều lần với cùng một $i$, mà lần nào cũng ra cùng một số cách. Vậy thì tính 1 lần rồi lưu lại thôi! Cho bạn nào đã biết cơ bản về quy hoạch động rồi thì ta có 4 bước như sau:
Bước 1: Xác định bài toán con
Gọi $F[i]$ với $0 \le i \le n + 1$ chính là số cách có thể để ta từ bờ bên trái tới được cọc thứ $i$. Ở bờ bên trái ta gọi là cọc thứ $0$, còn bờ bên phải chính là cọc thứ $n + 1$.
Bước 2: Xác định bài toán cơ sở
- Ở bờ bên trái tức cọc thứ 0: mặc định lúc đầu ta đang đứng ở đó rồi nên ta sẽ có $F[0] = 1$.
- Ở những cọc mục nát, tức $a[i] = 2$: vì ta sẽ không nhảy tới những cọc này, nên số cách tới cọc mục nát sẽ bằng 0, tức $F[i] = 0$. Ta sẽ khởi tạo mảng $F$ toàn bộ bằng 0 để tiện cho việc nếu gặp $a[i] = 2$ thì ta sẽ không phải xét nữa. Để làm điều đó, ta chỉ cần khai báo mảng $F$ là mảng toàn cục là chương trình sẽ tự gán mọi phần tử bằng 0 rồi.
- Cọc đầu tiên: nếu nó là cọc mục nát thì mặc định số cách tới nó bằng 0 rồi, còn nếu nó là cọc lung lay hay cọc tốt thì số cách tới nó đều bằng 1, vì để tới nó thì chỉ có thể từ cọc 0 ra mà.
- Cọc thứ 2: nếu nó là cọc mục nát thì mặc định bằng 0; nếu nó là cọc lung lay thì số cách tới nó bằng số cách tới cọc 1, vì cọc 2 lung lay nên chỉ có thể tới từ cọc 1; còn nếu nó là cọc tốt thì số cách tới cọc 2 bằng số cách tới cọc 1 cộng thêm 1, vì ta có thể từ cọc 1 sang cọc 2 hoặc từ cọc 0 nhảy thẳng sang cọc 2.
Vậy tổng kết lại các trường hợp cơ sở của ta sẽ là:
| $F[0] = 1$ | khởi tạo mọi $F[i] = 0$ (gặp $a[i] = 2$ thì không xét nữa) |
| $a[1] = 0$ hoặc $a[1] = 1$ | $F[1] = 1$ |
| $a[2] = 0$ | $F[2] = F[1] + 1$ |
| $a[2] = 1$ | $F[2] = F[1]$ |
Bước 3: Xác định đáp án của bài toán
Hiển nhiên đáp án của bài toán sẽ là $F[n + 1]$ rồi, vì ta đang cần tìm số cách để có thể từ bờ bên trái tới được bờ bên phải, tức là tới được cọc thứ $n + 1$ mà.
Bước 4: Xác định công thức truy hồi
Giờ giả sử ta đang xét cọc $i$. Nếu $a[i] = 0$, ta có thể tới từ cọc $i - 1$ và $i - 2$, và sẽ có thể tới được từ cọc $i - 3$ nếu $a[i - 3] = 0$ như đã phân tích ở phần vét cạn trên. Nếu ta có 10 cách để tới cọc $i - 1$ thì ta chỉ cần nhảy thêm 1 bước là tới cọc $i$ rồi, ta có 5 cách để tới cọc $i - 2$ thì chỉ cần nhảy thêm 1 bước từ $i - 2$ tới $i$ là đến cọc $i$ rồi, vậy chẳng phải số cách tới cọc $i$ là 15 cách. Vậy thì ta chắc chắn rằng nếu $a[i] = 0$ thì $F[i] = F[i - 1] + F[i - 2]$; và nếu $a[i - 3] = 0$ thì $F[i] \mathrel{+}= F[i - 3]$, vì lúc này cọc $i - 3$ là cọc tốt, giả dụ có 2 cách đến cọc $i - 3$ thì cũng sẽ có thêm 2 cách tới cọc $i$ nhờ từ cọc $i - 3$ ta nhảy thẳng tới cọc $i$.
Còn nếu $a[i] = 1$ thì sao? Thì chứng tỏ để tới cọc $i$ thì chỉ có thể đi từ cọc $i - 1$. Vậy số cách để tới cọc $i$ sẽ bằng số cách để tới cọc $i - 1$, hay $F[i] = F[i - 1]$.
Trường hợp $a[i] = 2$ thì ta sẽ không xét, mặc định $F[i]$ đã bằng 0 rồi.
- Nếu $a[i] = 0$: $F[i] = F[i - 1] + F[i - 2]$; nếu $a[i - 3] = 0$ thì $F[i] \mathrel{+}= F[i - 3]$.
- Nếu $a[i] = 1$: $F[i] = F[i - 1]$.
- Nếu $a[i] = 2$: $F[i] = 0$.
Minh hoạTính F từng cọc
Em nhập dãy loại cọc $a_1, a_2, \ldots, a_n$ (mỗi số là 0, 1 hoặc 2, tối đa 14 cọc) rồi bấm Tiếp để xem $F$ của từng cọc được cộng từ những cọc nào (mũi tên xanh là được cộng, ô gạch là không được):
CodeQuy hoạch động O(N)
Đây là source code cho bạn nào cần tham khảo cách làm trên của mình nha:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (ll)1e9;
ll f[1005];
int a[1005];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
a[0] = a[n + 1] = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
f[0] = 1;
if(a[1] == 0 || a[1] == 1){
f[1] = 1;
}
if(a[2] == 0){
f[2] = f[1] + 1;
}
else if(a[2] == 1){
f[2] = f[1];
}
for(int i = 3; i <= n + 1; ++i){
if(a[i] == 0){
f[i] = f[i - 1] + f[i - 2];
if(a[i - 3] == 0){
f[i] += f[i - 3];
}
f[i] %= mod;
}
else if(a[i] == 1){
f[i] = f[i - 1];
}
}
cout << f[n + 1];
return 0;
}MOD = int(1e9)
f = [0] * 1005
a = [0] * 1005
n = int(input())
a[0] = a[n + 1] = 0
arr = list(map(int, input().split()))
for i in range(1, n + 1):
a[i] = arr[i - 1]
f[0] = 1
if a[1] == 0 or a[1] == 1:
f[1] = 1
if a[2] == 0:
f[2] = f[1] + 1
elif a[2] == 1:
f[2] = f[1]
for i in range(3, n + 2):
if a[i] == 0:
f[i] = f[i - 1] + f[i - 2]
if a[i - 3] == 0:
f[i] += f[i - 3]
f[i] %= MOD
elif a[i] == 1:
f[i] = f[i - 1]
print(f[n + 1])Giải thích 1 số chỗ trong cách làm ở trên: for(int i = 3; ...) ta sẽ bắt đầu từ $i = 3$, vì $i = 0, 1, 2$ đã được ta khởi tạo ở trên trường hợp cơ sở, và khi ta bắt đầu từ $i = 3$ thì i - 3 sẽ không mang giá trị âm nữa nên không cần phải check $i - 3 \ge 0$ nữa. Nhánh $a[i] = 1$ không cần chia dư vì $F[i - 1]$ đã nhỏ hơn $10^9$ sẵn rồi; còn tổng 3 số nhỏ hơn $3 \cdot 10^9$ thì long long chứa thoải mái.
Đánh giá độ phức tạp của cách làm trên:
Chính xác là $O(2n)$ cho cả không gian (vì ta dùng 2 mảng) và thời gian (vì ta đọc vào xong rồi mới xử lý). Bạn nào muốn thì hoàn toàn có thể xử lý trong lúc đọc dữ liệu để tối ưu hơn nữa nha.
Nhận xét
Đăng nhận xét