题解 | #大撒币#

题目链接

大撒币

题目描述

在一个长为 $a$ 、宽为 $b$ 的矩形桌子上，Alice 和 Bob 轮流放置半径为 $r$ 的硬币。Alice 先手。放置硬币时必须满足两个条件：

硬币的所有点都必须在桌子边界之内。
新硬币不能与桌上已有的任何硬币重叠（允许边界接触）。

无法进行合法操作的玩家输掉游戏。假设双方都采取最优策略，判断谁将获胜。

解题思路

这是一个典型的公平组合游戏。在这类游戏中，胜负通常取决于游戏总共可以进行的操作次数的奇偶性。如果总操作数是奇数，先手方（Alice）必胜；如果是偶数，后手方（Bob）必胜。

问题的核心在于计算在一个 $a \cdot b$ 的桌面上，最多可以放置多少枚半径为 $r$ 的互不重叠的硬币。

虽然圆形的紧密堆积是一个复杂的数学问题，但我们可以通过一个简化的模型来解决这个博弈问题。我们可以认为，每个半径为 $r$ 的硬币，都近似地占据了一个边长为其直径 $2r$ 的正方形区域。

因此，问题可以转化为：在一个 $a \cdot b$ 的矩形中，最多可以放入多少个边长为 $2r$ 的正方形？

沿着长度为 $a$ 的边，我们最多可以并排摆放 floor(a / (2 * r)) 个这样的正方形。
沿着宽度为 $b$ 的边，我们最多可以并排摆放 floor(b / (2 * r)) 个。

所以，总共可以放置的硬币数量（即游戏的总步数）可以估算为： $total\_moves = \lfloor \frac{a}{2r} \rfloor \cdot \lfloor \frac{b}{2r} \rfloor$

在得到总步数后，我们只需要判断它的奇偶性：

如果 $total\_moves$ 是奇数，Alice 获胜。
如果 $total\_moves$ 是偶数，Bob 获胜。

特别地，如果桌子的长或宽小于硬币的直径（ $a < 2r$ 或 $b < 2r$ ），那么 floor 的结果将为 0，总步数也为 0。这是一个偶数，此时先手 Alice 无法放置任何硬币，直接输掉游戏，Bob 获胜。这个结论与我们的模型是自洽的。

代码

cpp
java
python

#include <iostream>

using namespace std;

int main() {
    long long a, b, r;
    cin >> a >> b >> r;
    
    long long d = 2 * r;
    
    if (a >= d && b >= d) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long r = sc.nextLong();
        
        long d = 2 * r;
        
        if (a >= d && b >= d) {
            System.out.println("Alice");
        } else {
            System.out.println("Bob");
        }
    }
}

def solve():
    a, b, r = map(int, input().split())

    d = 2 * r

    if a >= d and b >= d:
        print("Alice")
    else:
        print("Bob")

solve()

算法及复杂度

算法：数学、博弈论
时间复杂度：整个过程只涉及几次算术运算和判断，因此时间复杂度为 $\mathcal{O}(1)$ 。
空间复杂度：只需要常数个变量来存储输入和中间结果，空间复杂度为 $\mathcal{O}(1)$ 。