Hướng dẫn giải của [200 đề thầy Đức] Bài 52: Trò chơi đặt đĩa
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
Bàn hình chữ nhật $a \times b$, đặt các đĩa bán kính $r$ sao cho tâm đĩa nằm trong bàn và không đè lên đĩa khác. Chỉ cần xét vị trí đặt đĩa đầu tiên: nếu người đi trước không đặt được đĩa nào, họ thua; nếu đặt được, họ thắng nhờ chiến lược đối xứng.
Sub 1: Vét cạn (thử mọi vị trí) — ~O(ab)~
Thử mọi vị trí tâm đĩa đầu tiên trên lưới nửa đơn vị, kiểm tra vị trí có nằm trong bàn và có đúng là tâm bàn $(a/2, b/2)$ không. Đạt 20/20 test (chỉ đúng về kết quả, chạy nhanh vì giới hạn $a, b \le 100$).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, r;
cin >> a >> b >> r;
// Vét cạn: thử mọi vị trí tâm đĩa đầu tiên trên lưới nửa đơn vị (tọa độ nhân 2).
// Tọa độ thật = x/2, y/2. Vị trí hợp lệ: r <= x/2 <= a-r, r <= y/2 <= b-r.
// Người đi trước thắng nếu đặt được đĩa ở tâm bàn (a/2, b/2) (hợp lệ) rồi đối xứng.
bool first = false;
for (int x = 0; x <= 2 * a && !first; x++) {
for (int y = 0; y <= 2 * b && !first; y++) {
bool valid = (2 * r <= x) && (x <= 2 * (a - r)) && (2 * r <= y) && (y <= 2 * (b - r));
bool isCenter = (x == a) && (y == b); // (x/2, y/2) = (a/2, b/2)
if (valid && isCenter) first = true;
}
}
cout << (first ? "First" : "Second") << "\n";
return 0;
}
Sub 2: Chiến lược đối xứng qua tâm — ~O(1)~
Người đi trước đặt đĩa ở tâm bàn. Đĩa đặt ở tâm nằm trọn trong bàn khi $a/2 \ge r$ và $b/2 \ge r$, tức $2r \le a$ và $2r \le b$.
Sau đó, mỗi khi đối thủ đặt đĩa ở $p$, người đi trước đặt đĩa ở $2c - p$ (với $c$ là tâm bàn). Vị trí này luôn hợp lệ: nằm trong bàn vì đối xứng, không đè lên đĩa nào vì tập đĩa hiện có đối xứng qua $c$ và khoảng cách giữa $p$ và $2c - p$ bằng $2|p - c| \ge 2r$. Vì vậy người đi trước luôn còn nước đi, và người đi sau là người bị kẹt đầu tiên.
Nếu $2r > a$ hoặc $2r > b$ thì không đặt được đĩa nào, người đi trước thua ngay.
Bẫy cần chú ý: điều kiện là $2r \le a$ (không phải $2r < a$) vì các đĩa được phép chạm nhau và chạm biên.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, r;
cin >> a >> b >> r;
// Người đi trước đặt đĩa ở tâm bàn (a/2, b/2). Đĩa có bán kính r nằm trọn trong bàn
// khi a/2 >= r và b/2 >= r, tức 2r <= a và 2r <= b.
// Sau đó mỗi lần đối thủ đặt đĩa ở p, người đi trước đặt đối xứng qua tâm ở 2c - p
// (luôn hợp lệ), nên người đi trước luôn còn nước đi => thắng.
// Nếu không đặt được đĩa đầu tiên thì người đi trước thua ngay.
if (2 * r <= a && 2 * r <= b)
cout << "First\n";
else
cout << "Second\n";
return 0;
}
Bình luận