Hướng dẫn giải của [200 đề thầy Đức] Bài 8: Tom và Jerry
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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.
Hướng dẫn giải
Đây là trò chơi trừ theo ước: ai không đi được nước nào thì thua. Gọi một số n là thắng nếu người đang đi với n có nước đi dẫn đến số thua cho đối thủ.
Sub 1: Quy hoạch động vét cạn — ~O(N^2)~
Gọi win[n] = 1 nếu người đi lúc này với n viên thắng. Với mỗi n, thử mọi ước a < n: nếu win[n - a] = 0 thì win[n] = 1. Tính bảng từ n = 2 đến N lớn nhất trong các bộ dữ liệu. Đúng nhưng chậm, đạt 1/21 test (phần còn lại TLE).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
vector<long long> ns(T);
long long mx = 1;
for (auto &n : ns) {
cin >> n;
mx = max(mx, n);
}
// win[n] = 1 nếu người đang đi với số n sẽ thắng
// Vét cạn: thử mọi ước a < n, nếu có nước đi a mà đối thủ thua (win[n-a] = 0) thì thắng
vector<int> win(mx + 1, 0);
for (long long n = 2; n <= mx; n++)
for (long long a = 1; a < n; a++)
if (n % a == 0 && !win[n - a]) {
win[n] = 1;
break;
}
for (auto n : ns) cout << win[n] << "\n";
return 0;
}
Sub 2: Quy luật chẵn lẻ — ~O(1)~
- N chẵn: Tom trừ 1 để còn N - 1 lẻ.
- N lẻ: mọi ước a của N đều lẻ nên N - a là số chẵn khác 0, đối thủ nhận được một số chẵn và thắng. Với N = 1 không có nước đi nên Tom thua.
Vậy in 1 khi N chẵn và 0 khi N lẻ. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long n;
cin >> n;
// N chẵn: Tom trừ 1 còn N lẻ cho Jerry, Jerry luôn gặp N lẻ -> Tom thắng.
// N lẻ (N = 1 hoặc mọi ước a của N đều lẻ, N - a chẵn) -> Jerry thắng.
cout << (n % 2 == 0 ? 1 : 0) << "\n";
}
return 0;
}
Bình luận