Game with a Fraction

The losing-looking line is

$3p=2q,$

because that is exactly $\frac{p}{q}=\frac23$. The whole game is about whether Bob can force the path to hit this line. No gcd, no fraction reduction ceremony. Just cross-multiply and move on.

From research, the official Codeforces tutorial page exposes the intended solution condition in code as p < q && min(p / 2, q / 3) >= q - p, and accepted/explanation sources give the equivalent cleaner form $p<q$ and $3p\ge 2q$. These are the same condition, since with $d=q-p>0$:

$d\le \left\lfloor\frac p2\right\rfloor \iff 2(q-p)\le p \iff 2q\le 3p,$

and

$d\le \left\lfloor\frac q3\right\rfloor \iff 3(q-p)\le q \iff 2q\le 3p.$

So Bob wins exactly when

$p<q \quad\text{and}\quad 3p\ge 2q.$

Now prove it, because vibes are not a proof.

First, suppose $p\ge q$. Alice can keep the fraction at least $1$ whenever it matters. If $q>1$, she decreases $q$, making $p/q$ even larger. If Bob decreases $p$, the best he can do is restore something like equality; he cannot force the ratio down to $2/3$. Since $2/3<1$, the target is never reached. If $q=1$, the target is impossible anyway because $p/q$ is an integer. Alice wins.

Second, suppose $3p<2q$, meaning $p/q<2/3$. Alice decreases $p$ whenever $p>0$. After her move, the value of $3p-2q$ drops by $3$, so it is still negative. Bob has two possible replies:

• decreasing $p$ drops $3p-2q$ even more;
• decreasing $q$ increases $3p-2q$ by $2$.

But right after Alice's move it is at most $-3$, so after Bob decreases $q$ it is still at most $-1$. Thus Bob cannot hit $3p=2q$. Once $p=0$, the target is also impossible. Alice wins.

The only remaining region is

$p<q \quad\text{and}\quad 3p\ge 2q.$

Let $d=q-p>0$. Bob uses the simple annoying strategy: on every turn, he decreases the opposite variable from Alice. If Alice decreases $p$, Bob decreases $q$; if Alice decreases $q$, Bob decreases $p$. Therefore after each complete Alice+Bob round, both numbers have decreased by exactly $1$.

After $k$ full rounds, the state is

$(p-k, q-k).$

We want this to lie on the target line:

$\frac{p-k}{q-k}=\frac23.$

Cross-multiply:

$3(p-k)=2(q-k),$ $3p-3k=2q-2k,$ $k=3p-2q.$

In this region, $k\ge 0$. Also the target state is legal:

$p-k=p-(3p-2q)=2(q-p)=2d,$ $q-k=q-(3p-2q)=3(q-p)=3d.$

So after exactly $k$ rounds, the game reaches $(2d,3d)$, whose fraction is $2/3$. If $k=0$, Bob wins immediately because the initial fraction is already $2/3$. Otherwise, Bob forces it after some replies. Alice cannot dodge it; Bob is basically dragging both coordinates diagonally until the line catches them.

Therefore the answer is:

$\boxed{\text{Bob iff } p<q \text{ and } 3p\ge 2q.}$

The constraints go up to $10^{18}$, but $3p$ and $2q$ still fit in signed 64-bit integers. Using long long is fine.

Complexity per test case is $O(1)$ time and $O(1)$ memory.