题目描述
给你两个 正 整数 x
和 y
,分别表示价值为 75 和 10 的硬币的数目。
Alice 和 Bob 正在玩一个游戏。每一轮中,Alice 先进行操作,Bob 后操作。每次操作中,玩家需要拿出价值 总和 为 115 的硬币。如果一名玩家无法执行此操作,那么这名玩家 输掉 游戏。
两名玩家都采取 最优 策略,请你返回游戏的赢家。
样例
输入:x = 2, y = 7
输出:"Alice"
解释:
游戏一次操作后结束:
Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
输入:x = 4, y = 11
输出:"Bob"
解释:
游戏 2 次操作后结束:
Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
Bob 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
限制
1 <= x, y <= 100
算法
(思维题) $O(1)$
- 由于凑成价值总和 115 硬币的方式只有一种,即拿一个 75 的硬币和四个 10 的硬币,所以拿出价值总和为 115 的硬币的次数是固定的。
- 找到 $x$ 和 $y/4$ 下取整的最小值,即为能拿出价值总和为 115 的硬币的次数。
- 如果这个次数为奇数,则 Alice 获胜,否则 Bob 获胜。
时间复杂度
- 一次判断,时间复杂度为 $O(1)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
string losingPlayer(int x, int y) {
return min(x, y / 4) & 1 ? "Alice" : "Bob";
}
};