Lát Gạch
Đề bài
Có một khoảng sân hình chữ nhật kích thước $2 \times n$ ô vuông, gồm 2 hàng và $n$ cột. Đánh số hàng từ 1 đến 2 theo thứ tự từ trên xuống dưới, đánh số cột từ 1 đến $n$ theo thứ tự từ trái qua phải. Người ta muốn lát sân bằng gạch màu trắng và điểm xuyết một số ô gạch màu đen, mỗi ô vuông được lát bởi một viên gạch, sao cho không có hai viên gạch màu đen nào chung cạnh với nhau. Hỏi có tất cả bao nhiêu cách khác nhau để lát khoảng sân trên (hai cách lát sân được gọi là khác nhau nếu tồn tại tối thiểu một ô ở dòng $i$ cột $j$ được lát gạch màu trắng ở cách này và lát gạch màu đen ở cách kia).
Ví dụ với $n = 2$, ta có 7 cách lát sân sau đây:
Dữ liệu nhập: là một số nguyên $n$ $(1 \le n \le 1000)$.
Dữ liệu xuất: là số cách lát gạch khoảng sân theo yêu cầu trên. Số lượng này có thể rất lớn nên chỉ cần in ra 8 số cuối (mod $100\,000\,000$).
Giới hạn: thời gian 1 giây, bộ nhớ 128 MB.
2713Lờ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: cho 1 khoảng sân $2 \times n$ ô vuông, ta cần lát sân bằng 2 loại gạch là gạch trắng và gạch đen, sao cho không có 2 viên gạch đen nào chung cạnh. Hỏi có bao nhiêu cách khác nhau để lát khoảng sân? Vì kết quả rất lớn nên ta chỉ cần in ra phần dư của kết quả với $10^8$ thôi nha. Ví dụ thì các bạn nhìn hình 7 cách lát sân $2 \times 2$ ở đề bài là sẽ hiểu ngay.
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 – thử mọi cách lát
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ì đó.
Chuẩn bị mảng
Đầu tiên ta sẽ tạo 1 mảng kí tự a có kích thước $3 \times (n + 1)$, vì làm vậy ta sẽ xét được hai hàng 1, 2 và cột từ 1 tới $n$, sẽ dễ hiểu hơn. Ta quy định chữ w (white) là gạch trắng, chữ b (black) là gạch đen nhé. Tức là nếu a[i][j] = 'w' có nghĩa là tại hàng $i$ cột $j$ là viên gạch trắng; ngược lại nếu a[i][j] = 'b' có nghĩa là tại hàng $i$ cột $j$ là viên gạch đen.
Ta sẽ gán a[1][0] = a[2][0] = 'w': ta coi rằng những viên gạch ở ngoài cùng bên trái đang nằm cạnh cột 0 toàn gạch trắng để dễ xét.
Hàm Try(i, j, n)
Lúc đầu ta coi khoảng sân hình chữ nhật đang trống, không có viên gạch nào cả. Ta sẽ lần lượt xét từ cột 1 tới cột $n$, ở mỗi cột ta sẽ xét viên gạch ở trên trước rồi mới xét viên gạch ở dưới. Ta gọi hàm Try(i, j, n) sẽ giúp ta biết viên gạch ở hàng $i$ cột $j$ có thể chọn màu gì. Đầu tiên ta cần check $j \le n$ để đảm bảo ta đang xét viên gạch nằm trong khoảng sân, nếu đã thoả mãn rồi thì ta sẽ kiểm tra tiếp:
- $i = 1$ (đang ở hàng 1): ta check
a[i][j - 1]tức viên gạch trước đó có phải màu trắng không; nếu có ta sẽ gána[i][j] = 'b'tức viên gạch màu đen, rồi gọi đệ quy xuống viên gạch dưới tức làTry(2, j, n); không thì ta sẽ thôi không gán màu đen và không gọi đệ quy nữa. Sau đó ta sẽ gána[i][j] = 'w', vì viên gạch trắng không phụ thuộc viên gạch chung cạnh nên dù trường hợp nào ta cũng có thể lát gạch trắng; rồi gọi đệ quy xuống gạch dướiTry(2, j, n). - $i = 2$ (đang ở hàng 2): ta check
a[i][j - 1]vàa[i - 1][j]có đều bằng'w'không, tức là viên gạch ở đằng trước và viên gạch ở bên trên có phải gạch trắng không; nếu có ta sẽ gán gạch đen rồi gọi đệ quy lên viên gạch ở hàng trên cột tiếp theo, tức làTry(1, j + 1, n); không thì thôi, viên gạch đang xét không thể là gạch đen được. Sau đó ta gána[i][j] = 'w'vì gạch trắng lát được mà không cần điều kiện gì cả, rồi gọiTry(1, j + 1, n). - Ngược lại nếu $j > n$, tức là ta đã xét xong viên gạch cuối cùng ở hàng 2 cột $n$. Vậy chứng tỏ là đã có 1 cách lát sân, ta sẽ tăng biến đếm lên; nhớ chia dư ở mỗi lần tăng để tránh tràn số và ta sẽ không gọi đệ quy nữa.
Sau đây là source code cho các bạn tham khảo cách làm trên của mình nha:
Code vét cạn (TLE từ test 20)
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (ll)1e8;
char a[3][1001];
ll cnt = 0;
void Try(int i, int j, int n){
if(j <= n){
if(i == 1){
if(a[i][j - 1] == 'w'){
a[i][j] = 'b';
Try(2, j, n);
}
a[i][j] = 'w';
Try(2, j, n);
}
else{
if(a[i][j - 1] == 'w' && a[i - 1][j] == 'w'){
a[i][j] = 'b';
Try(1, j + 1, n);
}
a[i][j] = 'w';
Try(1, j + 1, n);
}
}
else{
cnt++;
cnt %= mod;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
a[1][0] = a[2][0] = 'w';
int n;
cin >> n;
Try(1, 1, n);
cout << cnt;
return 0;
}import sys
sys.setrecursionlimit(1000000)
mod = int(1e8)
a = [['w'] * 1001 for _ in range(3)]
cnt = 0
def Try(i, j, n):
global cnt
if j <= n:
if i == 1:
if a[i][j - 1] == 'w':
a[i][j] = 'b'
Try(2, j, n)
a[i][j] = 'w'
Try(2, j, n)
else:
if a[i][j - 1] == 'w' and a[i - 1][j] == 'w':
a[i][j] = 'b'
Try(1, j + 1, n)
a[i][j] = 'w'
Try(1, j + 1, n)
else:
cnt += 1
cnt %= mod
n = int(input())
a[1][0] = a[2][0] = 'w'
Try(1, 1, n)
print(cnt)Giải thích 1 số chỗ trong cách làm trên:
ios::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é). Bài này thì không cần lắm vì chỉ đọc vào 1 số $n$ thôi, nhưng khi code thì các bạn cứ cho vào để cho quen nha.cnt %= mod: cái này ta làm vậy là nhờ đồng dư thức nha, 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ếu ta cộng hết vào rồi mới chia dư thì ta sẽ bị tràn số đó, nên là ở mỗi lần cộng ta sẽ chia dư luôn.Try(1, 1, n): vì ta bắt đầu từ hàng 1 cột 1 nên ta sẽ cho $i$ và $j$ lúc đầu bằng 1.
Đánh giá độ phức tạp của cách làm trên:
Không gian đúng ra sẽ là $O(3 \cdot (n + 1))$, nhưng ở cách làm trên ta thấy $n$ tối đa bằng 1000 nên mình khai luôn biến toàn cục char a[3][1001] luôn rồi. Còn thời gian thì để mà tính chính xác thì mình khó có thể tính cho các bạn được, vì mỗi lá của cây đệ quy là đúng 1 cách lát, mà số cách lát tăng khoảng $2.4$ lần mỗi khi thêm 1 cột (lát nữa ở phần quy hoạch động các bạn sẽ thấy vì sao). Nếu làm theo cách vét cạn trên thì sẽ bị TLE ở test 20 nha; code trên chỉ chạy dưới 1s nếu $n < 20$ thôi.
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. Cho ae 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]$ $(0 \le i \le n)$ là số cách lát gạch với sân có kích thước $2 \times i$.
Bước 2: Xác định bài toán cơ sở
Ở trên ta gán a[1][0] = a[2][0] = 'w' đó chẳng phải là ta coi rằng nếu không có cột nào thì ta vẫn có 1 cách lát cho sân, tức là sân mà không có gì ($2 \times 0$) thì vẫn là 1 cách đó. Vậy $F[0] = 1$.
Giờ mình sẽ quy ước thế này cho các bạn nhìn nhé: ở mỗi khoảng sân có kích thước $2 \times i$, ta sẽ viết cột cuối của nó như sau:
- w/b(i): cột cuối bên trên là gạch trắng, bên dưới là gạch đen.
- b/w(i): cột cuối bên trên là gạch đen, bên dưới là gạch trắng.
- w/w(i): cột cuối cả 2 viên đều là gạch trắng.
(Không có b/b vì 2 viên đen chung cạnh dọc.) Vậy với khoảng sân $2 \times 1$ sẽ có 3 cách lát sân là $\{w/w(1), w/b(1), b/w(1)\}$ (vì cột cuối của khoảng sân $2 \times 1$ cũng chính là khoảng sân luôn). Vậy từ đó $F[1] = 3$.
Ta tổng kết lại có 2 bài toán cơ sở là $F[0] = 1$, $F[1] = 3$.
Bước 3: Xác định đáp án của bài toán
Hiển nhiên sẽ là $F[n]$ rồi, vì ta cần tìm số cách lát gạch cho sân có kích thước $2 \times n$ mà.
Bước 4: Xác định công thức truy hồi
Ta sẽ nhận ra một điều thế này: số cách để lát sân $2 \times i$ chính bằng số cách lát sân mà cột cuối là 2 viên gạch trắng + số cách lát sân mà cột cuối là trắng trên, đen dưới + số cách lát sân mà cột cuối là đen trên, trắng dưới. Ta tạm gọi tắt là:
$F[i] = F[w/w(i)]$ $+ F[w/b(i)]$ $+ F[b/w(i)]$
Giờ ta nhìn tiếp, bản chất của sân $2 \times i$ chính là sân $2 \times (i - 1)$ + thêm 1 cột có 2 hàng. Vậy ta sẽ xem cái cột thêm vào có thể đi sau những cột cuối nào (ô gạch chéo đỏ là không được vì 2 viên đen sẽ nằm cạnh nhau theo hàng ngang):
| Cột thứ $i$ thêm vào | Cột $i-1$ đứng trước được phép | Số cách |
|---|---|---|
w/w | $F[i-1]$ | |
w/b | $F[w/w(i-1)]$ $+ F[b/w(i-1)]$ | |
b/w | $F[w/w(i-1)]$ $+ F[w/b(i-1)]$ |
- Trường hợp 1 – cột thêm vào là w/w: 2 viên gạch trắng thì đương nhiên đi được với mọi cột trước đó, nên số cách là $F[w/w(i-1)]$ $+ F[w/b(i-1)]$ $+ F[b/w(i-1)]$ $= F[i-1]$.
- Trường hợp 2 – cột thêm vào là w/b: viên gạch dưới là đen nên viên gạch cạnh nó (ở cột trước, hàng dưới) bắt buộc phải là trắng, tức là đi được với w/w và b/w. Số cách: $F[w/w(i-1)]$ $+ F[b/w(i-1)]$.
- Trường hợp 3 – cột thêm vào là b/w: tương tự, số cách là $F[w/w(i-1)]$ $+ F[w/b(i-1)]$.
Ta cộng trường hợp 2 + trường hợp 3, đổi chỗ 1 chút:
$\underbrace{F[w/w(i-1)] + F[w/b(i-1)] + F[b/w(i-1)]}_{F[i-1]}$ $+ F[w/w(i-1)]$ $= F[i-1] + F[w/w(i-1)]$
Và $F[w/w(i-1)]$ thì tương tự trường hợp 1 ở trên, nó bằng $F[w/w(i-2)]$ $+ F[w/b(i-2)]$ $+ F[b/w(i-2)]$ $= F[i-2]$. Vậy trường hợp 2 + trường hợp 3 $= F[i-1] + F[i-2]$.
Từ đó suy ra số cách để lát sân $2 \times i$ = trường hợp 1 + trường hợp 2 + trường hợp 3 $= F[i-1] + F[i-1] + F[i-2]$:
Các bạn thử với $F[0] = 1$, $F[1] = 3$ thì $F[2] = 2 \cdot 3 + 1 = 7$, đúng với test case rồi đó. Vậy $F[3] = 2 \cdot 7 + 3 = 17$, đúng rồi. Tương tự thử với 4 rồi 5 thì vẫn đúng nha (so với code vét cạn ở trên). Vậy công thức đã đúng rồi đó.
Minh hoạĐếm theo kiểu cột cuối
Em nhập $n$ (tối đa 15) rồi bấm Tiếp để xem từng cột được thêm vào: số cách kết thúc bằng w/w, w/b, b/w được tính từ cột trước thế nào, và vì sao tổng luôn bằng $2 \cdot F[i-1] + F[i-2]$:
CodeQuy hoạch động O(n)
Sau đây là source code cho các bạ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)1e8;
ll f[1001];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
f[0] = 1;
f[1] = 3;
for(int i = 2; i <= n; ++i){
f[i] = 2 * f[i - 1] + f[i - 2];
f[i] %= mod;
}
cout << f[n];
return 0;
}mod = int(1e8)
f = [0] * 1001
n = int(input())
f[0] = 1
f[1] = 3
for i in range(2, n + 1):
f[i] = 2 * f[i - 1] + f[i - 2]
f[i] %= mod
print(f[n])Đánh giá độ phức tạp của cách làm trên:
Về không gian thì các bạn hoàn toàn có thể làm cách trên mà không cần mảng (chỉ cần giữ 2 giá trị $F[i-1]$, $F[i-2]$), nhưng mình sẽ làm như trên cho các bạn dễ hiểu nha. Lưu ý $2 \cdot F[i-1]$ $+ F[i-2] < 3 \cdot 10^8$ nên dùng long long (thậm chí int) đều không bị tràn.
Nhận xét
Đăng nhận xét