题解 | #大撒币#

这是一个经典的博弈论问题，通常被称为“圆桌硬币游戏”或“对称博弈”。

这个问题的核心在于利用几何对称性来制定必胜策略。

基本逻辑： 这是一个公平组合游戏（Impartial Game），游戏在有限步骤内结束，没有平局，且信息完全公开。我们需要判断先手（Alice）是否有必胜策略。

情况分析：

1. 无法放置第一枚硬币的情况： 如果桌子的长 或宽 小于硬币的直径 ，那么桌子上连一枚硬币都放不下。

   • 在这种情况下，作为先手的 Alice 没有任何合法的操作空间。
   • 根据游戏规则，无法进行操作的玩家判负。
   • 结论： Bob 获胜。

2. 可以放置至少一枚硬币的情况： 如果桌子足够大（即 且 ），Alice 可以利用对称性策略必胜。

   • 第一步（占领中心）： Alice 将第一枚硬币准确地放置在矩形桌子的几何中心。
   • 后续策略（中心对称）： 无论 Bob 接下来将硬币放在桌子的哪个位置，Alice 都在该位置关于桌子中心对称的地方放置一枚硬币。
   • 为什么这总是合法的？
     • 由于桌子是中心对称图形，且第一枚硬币占据了中心位置，剩余的可用空间也是关于中心对称的。
     • 如果 Bob 能在某个位置 合法放置一枚硬币（即不与现有硬币重叠且在边界内），那么根据对称性，位置 关于中心的对称点 也一定在边界内。
     • 同时，因为之前的状态（包括中心硬币和之前成对放置的硬币）都是中心对称的，所以如果 不与任何旧硬币重叠， 也不会与任何旧硬币重叠。
     • 此外， 和 不会重叠，除非它们是同一个位置（即中心），但中心已经被 Alice 的第一枚硬币占据了。
   • 结果： 只要 Bob 能做出一个合法操作，Alice 就能做出一个对应的对称操作。由于桌子面积有限，硬币数量无限但空间有限，游戏终将结束。Bob 最终会面临无处可放的局面。
   • 结论： Alice 获胜。

代码实现：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a, b, r;
    cin >> a >> b >> r;

    if (2 * r > a || 2 * r > b) {
        cout << "Bob\n";
    } else {
        cout << "Alice\n";
    }
}