3222. 求出硬币游戏的赢家
题目描述
给你两个 正 整数 x 和 y ，分别表示价值为 75 和 10 的硬币的数目。
Alice 和 Bob 正在玩一个游戏。每一轮中，Alice 先进行操作，Bob 后操作。每次操作中，玩家需要拿走价值 总和 为 115 的硬币。如果一名玩家无法执行此操作，那么这名玩家 输掉 游戏。
两名玩家都采取 最优 策略，请你返回游戏的赢家。
示例 1：
输入：x = 2, y = 7
输出："Alice"
解释：
游戏一次操作后结束：
- Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
示例 2：
输入：x = 4, y = 11
输出："Bob"
解释：
游戏 2 次操作后结束：
- Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
- Bob 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
提示：
1 <= x, y <= 100
解法
方法一：数学
由于每一轮的操作，会消耗 $2$ 枚价值为 $75$ 的硬币和 $8$ 枚价值为 $10$ 的硬币，因此，我们可以计算得到操作的轮数 $k = \min(x / 2, y / 8)$，然后更新 $x$ 和 $y$ 的值，此时 $x$ 和 $y$ 就是经过 $k$ 轮操作后剩余的硬币数目。
如果 $x > 0$ 且 $y \geq 4$，那么 Alice 还可以继续操作，此时 Bob 就输了，返回 "Alice"；否则，返回 "Bob"。
时间复杂度 $O(1)$，空间复杂度 $O(1)$。
Python3
class Solution:
def losingPlayer(self, x: int, y: int) -> str:
k = min(x // 2, y // 8)
x -= k * 2
y -= k * 8
return "Alice" if x and y >= 4 else "Bob"
Java
class Solution {
public String losingPlayer(int x, int y) {
int k = Math.min(x / 2, y / 8);
x -= k * 2;
y -= k * 8;
return x > 0 && y >= 4 ? "Alice" : "Bob";
}
}
C++
class Solution {
public:
string losingPlayer(int x, int y) {
int k = min(x / 2, y / 8);
x -= k * 2;
y -= k * 8;
return x && y >= 4 ? "Alice" : "Bob";
}
};
Go
func losingPlayer(x int, y int) string {
k := min(x/2, y/8)
x -= 2 * k
y -= 8 * k
if x > 0 && y >= 4 {
return "Alice"
}
return "Bob"
}
TypeScript
function losingPlayer(x: number, y: number): string {
const k = Math.min((x / 2) | 0, (y / 8) | 0);
x -= k * 2;
y -= k * 8;
return x && y >= 4 ? 'Alice' : 'Bob';
}