[_-0 C] 猜数游戏：应对随机错误的挑战

题目背景

小 \mathfrak{f} 和小 \mathfrak{g} 在玩猜数游戏，但是因为风声太大，他们听不清楚对方说的话……

题目描述

评测机在区间 [1,n] 中等概率随机地选择一个整数 x，你的任务是猜测这个数。

你可以每次给出一个 [1,n] 中的整数 y，询问 y 和 x 的大小关系。你最多可以询问 q 次。

但是，由于某些原因，评测机有 p% 的概率会出错。

具体地说：

如果 y=x，那么评测机返回 =。
如果 y\ne x，且当前已经是第 q 次询问，那么评测机返回 !。
得到以上两种结果后，你应当停止询问。
如果 y>x，那么评测机有 (100-p)% 的概率返回 >，有 p% 的概率返回 <。
如果 y<x，那么评测机有 (100-p)% 的概率返回 <，有 p% 的概率返回 >。

每次询问，你需要向标准输出输出一个 [1,n] 中的整数，然后清空缓冲区。

你可以使用如下语句来清空缓冲区：

对于 C/C++：fflush(stdout)；
对于 C++：std::cout << std::flush；
对于 Java：System.out.flush()；
对于 Python：stdout.flush()；
对于 Pascal：flush(output)；
对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。

然后你需要从标准输入中输入一个字符，代表评测机返回的结果。

输入格式

开始询问之前，一行，三个用空格分隔的整数 n,p,q。

对于每一次询问，一行，一个字符，一定是 =，!，>，< 四者之一。

输出格式

对于每一次询问，一行，一个 [1,n] 中的整数。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

样例输出 #3

50

25

提示

样例 $1$ 解释：

此时该测试点的状态为 AC。

样例 $2$ 解释：

x=37,y=50 时，y>x，有 10% 的概率输出 <，恰好输出了 <。

样例 $3$ 解释：

此时该测试点的状态为 WA。

本题采用捆绑测试。

考虑到本题具有一定的随机性，每个 Subtask 下设有 $5$ 个测试点，你只需通过其中至少 $3$ 个测试点即可得到该 Subtask 对应的分数。

本题不使用子任务依赖。

对于所有数据，n=10^{18}。

| 编号 | 分值 | p= | q= | 时限 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | $5$ | $0$ | $60$ | \texttt{1s} | | $1$ | $10$ | $10$ | $500$ | \texttt{1s} | | $2$ | $10$ | $25$ | $2000$ | \texttt{1s} | | $3$ | $15$ | $25$ | $1000$ | \texttt{1s} | | $4$ | $20$ | $25$ | $700$ | \texttt{1s} | | $5$ | $10$ | $25$ | $400$ | \texttt{1s} | | $6$ | $10$ | $40$ | $2500$ | \texttt{1s} | | $7$ | $10$ | $45$ | $10000$ | \texttt{1s} | | $8$ | $5$ | $48$ | $62500$ | \texttt{3s} | | $9$ | $5$ | $49$ | $250000$ | \texttt{10s} | 用C++解内容：```cpp #include #include using namespace std;

int main() { int n, p, q; cin >> n >> p >> q;

int l = 1, r = n;
while (true) {
    int mid = (l + r) / 2;
    cout << mid << endl;
    char result;
    cin >> result;
    if (result == '=') {
        break;
    } else if (result == '<') {
        r = mid - 1;
    } else if (result == '>') {
        l = mid + 1;
    } else if (result == '!') {
        q--;
        if (q == 0) {
            break;
        }
    }
}

return 0;

}

猜数游戏：如何应对随机错误的挑战