Hướng dẫn giải của [200 đề thầy Đức] Bài 88: Chơi 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.
Hướng dẫn giải
Loại tốt nhất là A (dạng 4n + 1). Chỉ cần xét tăng HP thêm a ∈ {0, 1, 2} để đạt loại cao nhất, và chọn a nhỏ nhất nếu có nhiều cách.
Sub 1: Vét cạn thử a — ~O(q)~
Với mỗi truy vấn, thử lần lượt a = 0, 1, 2, xếp hạng loại của x + a rồi giữ kết quả tốt nhất. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
// Xếp hạng loại: A (4n+1) = 4 > B (4n+3) = 3 > C (4n+2) = 2 > D (4n) = 1
int hangLoai(int hp) {
int r = hp % 4;
if (r == 1) return 4;
if (r == 3) return 3;
if (r == 2) return 2;
return 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
// Vét cạn: thử a = 0, 1, 2; chọn a cho loại cao nhất (a nhỏ nhất nếu bằng nhau)
int aTot = 0, hangTot = hangLoai(x);
for (int a = 1; a <= 2; a++) {
int h = hangLoai(x + a);
if (h > hangTot) {
hangTot = h;
aTot = a;
}
}
char ten[] = {'?', 'D', 'C', 'B', 'A'};
cout << aTot << " " << ten[hangTot] << "\n";
}
return 0;
}
Sub 2: Công thức theo số dư mod 4 — ~O(q)~
Xét x mod 4: dư 1 là A với a = 0; dư 0 cần +1 để thành A; dư 3 cần +2 để thành A; dư 2 không thể thành A với a ≤ 2 nên tăng +1 thành B. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Với x mod 4, tăng ít nhất có thể để đạt loại A (nếu được) hoặc B
// x = 0 (loại D): +1 -> A
// x = 1 (loại A): đã là A, +0
// x = 2 (loại C): +1 -> B (+3 mới ra A, không được)
// x = 3 (loại B): +2 -> A
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
int r = x % 4;
if (r == 0) cout << "1 A\n";
else if (r == 1) cout << "0 A\n";
else if (r == 2) cout << "1 B\n";
else cout << "2 A\n";
}
return 0;
}
Bình luận