CF-1079-C. Game with a Fraction · znzryb
## 题目大意
**题目：** C. 带有分数的游戏
**题意：**
Alice 和 Bob 玩一个游戏，初始有两个整数 $p$ 和 $q$。Alice 先手，两人轮流进行操作。
每回合玩家可以执行以下操作之一：
1. 将 $p$ 减少 1（需满足 $p > 0$）。
1. 将 $q$ 减少 1（需满足 $q > 1$）。
游戏在 $p=0$ 且 $q=1$ 时结束。
**胜负判定：**
- **Bob 获胜**：如果在游戏过程中的**任意时刻**（包括初始状态），分数 $\frac{p}{q}$ 的值等于 $\frac{2}{3}$。
- **Alice 获胜**：如果游戏结束时 Bob 仍未获胜。
假设双方都采取最优策略，判断谁是赢家。
**样例解释：**
- 输入 `4 6`：初始 $\frac{4}{6} = \frac{2}{3}$，Bob 立即获胜。
- 输入 `10 14`：双方博弈过程中，可能会到达状态 $p=8, q=12$，此时 $\frac{8}{12} = \frac{2}{3}$，Bob 获胜。
- 输入 `15 15`：Alice 存在必胜策略，使得游戏过程中分数永远不等于 $\frac{2}{3}$，最终 Alice 获胜。
## 思路讲解
不难推出，3P 小于2Q 时无答案。（糖水不等式就是把，这个糖水不等式就是把糖从溶液里面抠出来，溶液质量和糖的质量它都会减。按照实际生活常识，我们知道此时溶液浓度肯定是下降的，因为你少加点糖，那溶液浓度总归是减的呀，不会增呀，对吧？）
::: AI 讲解
你提到的糖水不等式其实**两个方向都能用**，而且恰好就是切入点。
## 糖水不等式回顾
如果 $\frac{p}{q} < 1$（即 $p < q$），那么分子分母同时减去相同正数后，分数**变小**：
$$
\frac{p - 1}{q - 1} < \frac{p}{q} \quad (\text{当}\ p < q)
$$
如果 $\frac{p}{q} \geq 1$（即 $p \geq q$），则反过来，分数**变大**（或不变）。
## 镜像策略 = 分子分母同时减 1
Bob 的镜像策略效果是：**每一轮** $p$ **和** $q$ **各减 1**，Alice 无法干预。那每一轮分数从 $\frac{p}{q}$ 变成 $\frac{p-1}{q-1}$。
## $p/q > 2/3$ 时的两种情况
**情况一：**$\frac{2}{3} < \frac{p}{q} < 1$**（即** $p < q$**）**
分数在 $\frac{2}{3}$ 和 $1$ 之间。由糖水不等式，每轮分子分母同减 1 后分数**变小**，朝着 $\frac{2}{3}$ 靠近。而 $v = 3p - 2q$ 每轮恰好减 1（整数），所以不会"跳过" $\frac{2}{3}$，一定会**精确命中** $v = 0$。Bob 赢。
**情况二：**$\frac{p}{q} \geq 1$**（即** $p \geq q$**）**
分数 $\geq 1$。由糖水不等式，分子分母同减 1 后分数**变大**（远离 $\frac{2}{3}$）。而且 $q$ 的余量不够——$q$ 会先降到 1，此后只能减 $p$，$v$ 每步变化 $-3$，从 $v \equiv 1 \pmod{3}$ 开始逐步减，**永远跳过** $0$。Alice 赢。
## 总结
| 条件 | 糖水不等式效果 | 结果 |
| --- | --- | --- |
| $\frac{p}{q} = \frac{2}{3}$ | 已经命中 | Bob 赢 |
| $\frac{p}{q} < \frac{2}{3}$ | 分数远离 $\frac{2}{3}$（变更小） | Alice 赢 |
| $\frac{2}{3} < \frac{p}{q} < 1$ | 分数靠近 $\frac{2}{3}$（变小） | Bob 赢 |
| $\frac{p}{q} \geq 1$ | 分数远离 $\frac{2}{3}$（变大） | Alice 赢 |
分界线就是 $\frac{p}{q} = 1$，即 $p = q$。
所以判定条件只有一句话：**Bob 赢当且仅当** $3p \geq 2q$ **且** $p < q$。糖水不等式是两个方向上统一的判据。
:::
::: AI 讲解 2
好问题。糖水不等式只告诉我们方向（变小），不保证精确命中 $\frac{2}{3}$。真正的保证来自 $v = 3p - 2q$ 这个量。
## 为什么一定能精确命中
镜像策略下，每轮 $p$ 和 $q$ 各减 1，所以：
$$
v' = 3(p-1) - 2(q-1) = 3p - 2q - 1 = v - 1
$$
$v$ 是**整数**，每轮**恰好减 1**。
起点 $v_0 = 3p - 2q > 0$（正整数），每轮减 1：
$$
v_0,\quad v_0 - 1,\quad v_0 - 2,\quad \ldots,\quad 2,\quad 1,\quad 0
$$
它是逐个整数递减的，**不可能跳过 0**。所以 $v = 0$ 一定会被经过。
## 和糖水不等式的关系
糖水不等式告诉你的是**分数** $\frac{p}{q}$ 在变小，但分数是有理数，变小不代表能精确等于某个值（比如你可能担心 $0.672, 0.669, 0.665, \ldots$ 这样跳过了 $\frac{2}{3} = 0.6\overline{6}$）。
但 $v = 3p - 2q$ 是整数世界的东西。$\frac{p}{q} = \frac{2}{3}$ 等价于 $v = 0$。每轮 $v$ 减 1，从正整数出发，**必然经过 0**。这就是精确命中的保证。
## 还要确认的一件事
$v$ 从 $v_0$ 减到 $0$ 需要 $v_0$ 轮，即 $2v_0$ 步。游戏总共有 $p + q - 1$ 步，所以需要：
$$
2v_0 \leq p + q - 1
$$
代入 $v_0 = 3p - 2q$：
$$
2(3p - 2q) \leq p + q - 1 \iff 5p \leq 5q - 1 \iff p < q
$$
这就是为什么 $p < q$ 是必要且充分的——它保证游戏在 $v$ 到达 $0$ 之前**不会提前结束**。
所以结论很清晰：$v$ 每轮整数减 1，不会跳过；$p < q$ 保证游戏撑得到那一轮。两个条件合在一起，$v = 0$ 一定会被命中。
:::
那么 P 除以 Q 大于2/3是比较棘手的这个情况。然后我们又进行了一下分类讨论，然后说明了 P 除以 Q 大于等于一的时候，一定是没有解的。这是根据糖水不等式，其实就是颠倒个个嘛，就是颠倒个，就是水和糖不一样了，那么这个结果 也也是自然是不一样的。然后是 p 除以 q 大于2/3小于一的时候，那么就是这个时候是 Bob 一定是赢的，因为 我们写在这个图片里面了，它一定有一个合法解。
## AC代码
AC
[https://codeforces.com/contest/2197/submission/362464859](https://codeforces.com/contest/2197/submission/362464859)
::: 源代码
```cpp
/**
* Problem: C. Game with a Fraction
* Contest: Codeforces Round 1079 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2197/problem/C
* Created: 2026-02-11 22:58:39
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll p,q;
cin >> p >> q;
__int128 a = (__int128)3 * p;
__int128 b = (__int128)2 * q;
__int128 c = (__int128)3 * q;
if (b <= a && a < c) cout << "Bob\n";
else cout << "Alice\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
*/
```
:::
## 心路历程（WA，TLE，MLE……）