Hướng dẫn giải của [CSES 1099] Stair Game
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.
Trò chơi này tương ứng với nim trong đó ta chỉ lấy mỗi giá trị ở vị trí chẵn vào tổng xor. Chính xác hơn, ta chỉ xét các bậc có chỉ số chẵn.
Nếu một người chơi di chuyển ~c~ đồng xu từ bậc ~k~ xuống bậc ~k-1~ với ~k~ lẻ, đối thủ luôn có thể hủy nước đi đó bằng cách di chuyển ~c~ đồng xu từ bậc ~k-1~ xuống ~k-2~ ngay sau đó. Do đó, ta có thể bỏ qua các bậc có chỉ số lẻ và chơi nim chỉ với các bậc có chỉ số chẵn.
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
for (int ti = 1; ti <= t; ti++) {
int n;
cin >> n;
int sum = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (i % 2 == 0) sum ^= x;
}
cout << (sum != 0 ? "first" : "second") << "\n";
}
}
Chương trình tham khảo
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
for (int ti = 1; ti <= t; ti++) {
int n;
cin >> n;
int sum = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (i % 2 == 0) sum ^= x;
}
cout << (sum != 0 ? "first" : "second") << "\n";
}
}
Bình luận