【ICPC】2022 昆明站 K题 题解及推导过程

题目大意

G准备玩 $n$ 场游戏，它心中有个胜率 $x = \frac{a}{b}$，如果当前胜场比大于 $x$，那么他就会赢，否则它就会输。给定 $a, b, n$，求他能赢多少局。

题目链接

思路

图中画出了胜场比变化图。如果当前胜场比 $s > x$，那么我们就会输，反之我们就会赢！进行第 $n$ 局时，假如我们知道了此时的 $s$，那么我们就能得本局是否会赢。

那么如何寻找 $s_{n-1}$？它在 $x$ 的两侧。比如 $x = \frac{2.7}{4}$，$s_{n-1}$ 的候选为 $\frac{2}{4}$ 或 $\frac{3}{4}$。

• 假如 $s_{n-1} = \frac{2}{4}$，$s \le x$，第 $n$ 局就会赢，$ans = \frac{3}{5}$。
• 假如 $s_{n-1} = \frac{3}{4}$，$s > x$，那么第 $n$ 局就会输，$ans = \frac{3}{5}$。

可以发现，第 $n$ 局的答案和 $s_{n-1}$ 无关，即

$$ans = \lfloor(n-1) \cdot x\rfloor + 1$$

这个式子表示我们假设第 $n-1$ 局输掉了比赛，那么我们第 $n$ 局就会赢回来一局。

#include <cstdio>
#include <iostream>
using namespace std;

int main()
{
    int T;
    long long a, b, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%lld%lld%lld", &n, &a, &b);
        printf("%lld\n",(n - 1) * a / b + 1);
    }
    return 0;
}