CF-1079-C. Game with a Fraction

题目大意

题目： C. 带有分数的游戏

题意：
Alice 和 Bob 玩一个游戏，初始有两个整数 $p$ 和 $q$。Alice 先手，两人轮流进行操作。
每回合玩家可以执行以下操作之一：

1. 将 $p$ 减少 1（需满足 $p > 0$）。

2. 将 $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

源代码

/**
 * 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……）