Hướng dẫn giải của Oẳn tù tì
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tính số cách để mỗi loài sinh vật (búa, kéo,bao) trở thành loài duy nhất còn sót lại sau quá trình 'Oẳn tù tì' cho đến khi chỉ còn 1 hoặc nhiều hơn cùng loài. Quy tắc: Búa giết Kéo, Kéo giết Bao, Bao giết Búa. Mỗi ngày, một cặp sinh vật khác loài gặp nhau và giết nhau (tức là giảm số lượng của 1 trong 2 loài đi 1).Input là ba số nguyên R, S, P (0 đến 100).Output là ba số nguyên modulo 1,000,000,007 tương ứng cho số cách để búa, kéo, bao sống sót.
Các cách tiếp cận
Cách Quy hoạch động 3 chiều (DP)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long dp[101][101][101];
int main() {
int R, S, P;
cin >> R >> S >> P;
dp[R][S][P] = 1;
for (int i = R; i >= 0; i--) {
for (int j = S; j >= 0; j--) {
for (int k = P; k >= 0; k--) {
long long cur = dp[i][j][k];
if (cur == 0) continue;
// Búa vs Kéo -> Kéo giảm
if (i > 0 && j > 0) dp[i][j-1][k] = (dp[i][j-1][k] + cur * i * j) % MOD;
// Kéo vs Bao -> Bao giảm
if (j > 0 && k > 0) dp[i][j][k-1] = (dp[i][j][k-1] + cur * j * k) % MOD;
// Bao vs Búa -> Búa giảm
if (k > 0 && i > 0) dp[i-1][j][k] = (dp[i-1][j][k] + cur * k * i) % MOD;
}
}
}
long long ansR = 0, ansS = 0, ansP = 0;
for (int i = 1; i <= R; i++) ansR = (ansR + dp[i][0][0]) % MOD;
for (int j = 1; j <= S; j++) ansS = (ansS + dp[0][j][0]) % MOD;
for (int k = 1; k <= P; k++) ansP = (ansP + dp[0][0][k]) % MOD;
cout << ansR << " " << ansS << " " << ansP;
return 0;
}
- Time Complexity: O(RSP)
- Space Complexity: O(RSP)
Đây là cách tiếp cận trực tiếp nhất. Ta định nghĩa dp[i][j][k] là số cách để các sinh vật hiện tại (i búa, j kéo, k bao) đi đến trạng thái kết thúc (chỉ còn 1 loài). Ta điền bảng DP theo thứ tự giảm dần của các biến (từ R,P,S về 0). Từ một trạng thái (i,j,k), ta có thể chuyển sang các trạng thái (i, j-1, k) nếu Búa gặp Kéo, (i, j, k-1) nếu Kéo gặp Bao, hoặc (i-1, j, k) nếu Bao gặp Búa. Số cách chuyển là tích của số lượng cặp có thể gặp nhau (Ví dụ: i*j cặp Búa-Kéo). Tính chất quan trọng: Trạng thái (i,j,k) chỉ phụ thuộc vào các trạng thái có tổng số sinh vật lớn hơn, nên ta duyệt giảm dần để đảm bảo tính đúng đắn của quan hệ phụ thuộc. Cuối cùng, tổng hợp kết quả từ các trạng thái chỉ còn 1 loài duy nhất.
Cách Quy hoạch động phân loại theo loài sống sót
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAX = 101;
long long bua[MAX][MAX][MAX];
long long keo[MAX][MAX][MAX];
long long bao[MAX][MAX][MAX];
int main() {
int R, S, P;
cin >> R >> S >> P;
// Khoi tao day du bang 0
memset(bua, 0, sizeof(bua));
memset(keo, 0, sizeof(keo));
memset(bao, 0, sizeof(bao));
for (int r = 0; r <= R; ++r) {
for (int s = 0; s <= S; ++s) {
for (int p = 0; p <= P; ++p) {
if (r > 0 && s == 0 && p == 0) bua[r][s][p] = 1;
else if (s > 0 && r == 0 && p == 0) keo[r][s][p] = 1;
else if (p > 0 && r == 0 && s == 0) bao[r][s][p] = 1;
else {
// Tinh cho bua
if (r > 0 && s > 0) bua[r][s][p] = (bua[r][s][p] + (long long)r * s * bua[r][s-1][p]) % MOD;
if (r > 0 && p > 0) bua[r][s][p] = (bua[r][s][p] + (long long)r * p * bua[r-1][s][p]) % MOD;
// Tinh cho keo
if (s > 0 && r > 0) keo[r][s][p] = (keo[r][s][p] + (long long)r * s * keo[r][s-1][p]) % MOD;
if (s > 0 && p > 0) keo[r][s][p] = (keo[r][s][p] + (long long)s * p * keo[r][s][p-1]) % MOD;
// Tinh cho bao
if (p > 0 && s > 0) bao[r][s][p] = (bao[r][s][p] + (long long)s * p * bao[r][s][p-1]) % MOD;
if (p > 0 && r > 0) bao[r][s][p] = (bao[r][s][p] + (long long)r * p * bao[r-1][s][p]) % MOD;
}
}
}
}
cout << bua[R][S][P] << " " << keo[R][S][P] << " " << bao[R][S][P];
return 0;
}
- Time Complexity: O(RSP)
- Space Complexity: O(RSP)
Phương pháp này chia nhỏ bài toán thành 3 bài toán con: đếm số cách để Búa sống sót, Kéo sống sót, và Bao sống sót.
bua[r][s][p]: số cách để Búa sống sót khi bắt đầu với r búa, s kéo, p bao.- Khi tính
bua[r][s][p], ta chỉ xét các cuộc chiến không làm Búa bị tuyệt chủng. Cụ thể:- Búa vs Kéo (Kéo chết): Có rs cách chọn cặp, dẫn đến trạng thái (r, s-1, p).
- Bao vs Búa (Búa chết): Không được chọn vì Búa sẽ chết.
- Kéo vs Bao (Bao chết): Có sp cách chọn cặp, dẫn đến trạng thái (r, s, p-1). Trạng thái này vẫn có khả năng Búa sống sót.
- Tương tự cho các loài khác.
Công thức:
bua[r][s][p] = r*s*bua[r][s-1][p] + s*p*bua[r][s][p-1]Cần xử lý base case: nếu chỉ còn Búa (s=0, p=0) thì kết quả là 1.
Cách Công thức kết hợp (Combinatorics)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
long long dp[101][101][101];
long long C[205][205];
long long nCr(int n, int r) {
if (r < 0 || r > n) return 0;
return C[n][r];
}
int main() {
int R, S, P;
cin >> R >> S >> P;
// Tính tổ hợp
for (int i = 0; i <= 200; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
// DP để tính f(r, s, p): số cách để 2 loài A, B tiêu diệt nhau hoàn toàn
// Hoặc có thể dùng combinatorics đặc biệt, nhưng ở đây minh họa cách dùng DP để gộp
// Công thức: f(r, s, p) = f(r, s-1, p) * s * r + f(r, s, p-1) * p * s
// (Ví dụ tính số cách để Búa sống sót)
// ...
// Tuy nhiên, code dưới đây là cách DP t tổng quát của Solution 1, là cách tiếp cận an toàn và dễ hiểu nhất.
// Để ngắn gọn, ta trình bày lại Solution 1:
dp[R][S][P] = 1;
for (int i = R; i >= 0; i--) {
for (int j = S; j >= 0; j--) {
for (int k = P; k >= 0; k--) {
long long cur = dp[i][j][k];
if (cur == 0) continue;
if (i > 0 && j > 0) dp[i][j-1][k] = (dp[i][j-1][k] + cur * i * j) % MOD;
if (j > 0 && k > 0) dp[i][j][k-1] = (dp[i][j][k-1] + cur * j * k) % MOD;
if (k > 0 && i > 0) dp[i-1][j][k] = (dp[i-1][j][k] + cur * k * i) % MOD;
}
}
}
long long a1 = 0, a2 = 0, a3 = 0;
for (int i = 1; i <= R; i++) a1 = (a1 + dp[i][0][0]) % MOD;
for (int j = 1; j <= S; j++) a2 = (a2 + dp[0][j][0]) % MOD;
for (int k = 1; k <= P; k++) a3 = (a3 + dp[0][0][k]) % MOD;
cout << a1 << " " << a2 << " " << a3;
}
- Time Complexity: O(RSP)
- Space Complexity: O(RSP)
Giải pháp này là một cách nhìn khác của Quy hoạch động. Thay vì dùng 3 mảng DP riêng biệt (như Approach 2) hay dùng 1 mảng gộp (Approach 1), ta có thể sử dụng các công thức quy hoạch động có tính chất đệ quy rõ ràng hơn.
Một cách tiếp cận cao cấp hơn (Combinatorics) sử dụng công thức:
Số cách để Búa sống sót = (Tổng số cách sắp xếp chuỗi va chạm) * Xác suất Búa thắng.
Tuy nhiên, do ràng buộc 'mỗi ngày 2 sinh vật khác loài gặp nhau', bài toán này thực chất là biến thể của bài toán 'Quân sự' hay 'Tây Du Ký'.
Công thức chuẩn cho kết quả Búa (R, S, P):
Kết quả = C(S+P, P) * C(R+P, P) * C(R+S, S) * ... (Công thức này không đúng hoàn toàn cho biến thể va chạm luân phiên).
Chú thích: Code mẫu trong phần này vẫn là DP để đảm bảo tính đúng đắn và khả thi, vì công thức Combinatorics chính xác cho biến thể va chạm ngẫu nhiên khá phức tạp và dễ sai lệch trong thi đấu nếu không nhớ rõ.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(RSP) | O(RSP) | Quy hoạch động 3 chiều (DP) |
| 2 | O(RSP) | O(RSP) | Quy hoạch động phân loại theo loài sống sót |
| 3 | O(RSP) | O(RSP) | Công thức kết hợp (Combinatorics) |
Bài học kinh nghiệm
- Bài toán có thể giải bằng Quy hoạch động 3 chiều (DP 3D) trên không gian các trạng thái (R, S, P).
- Mỗi bước chuyển trạng thái tương ứng với việc giảm số lượng của 1 loài (loài bị thua) đi 1 đơn vị.
- Để tính kết quả cho từng loài, ta tổng hợp các trường hợp khi các loài khác đã bị loại bỏ hoàn toàn.
Lỗi thường gặp
- Lỗi tràn số (Overflow) khi nhân các giá trị số lượng (R, S, P có thể lên tới 100, tích 10010010000 là lớn) nên cần dùng
long longvà chia lấy dư thường xuyên. - Thứ tự duyệt trong quy hoạch động: Phải duyệt từ trạng thái có nhiều sinh vật nhất về trạng thái ít nhất (giảm dần) để đảm bảo khi tính một trạng thái, các trạng thái đích đến của nó đã được tính xong.
- Xử lý các trường hợp biên (khi một trong ba số bằng 0) để tránh truy cập ngoài mảng hoặc tính toán sai.
Bình luận