CF1624 F.Interacdive Problem【二分】

题目链接：codeforces 1624F

题意

已知 ，猜数字 。

对于每次询问：

  • + c：返回。

题解

二分，每次加的 为到下一个 所需的值，然后再去判断这个整数 与返回的 的大小，每次搜索后，保证 是 的整数倍。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int l = 1, r = n-1, mid;
    while (l < r) {
        mid = (l+r+1) >> 1;
        int c = n - mid % n, k = mid/n + 1;
        cout << "+ " << c << endl;
        int p; cin >> p;
        if (p >= k) {
            l = mid;
        } else {
            r = mid-1;
        }
        l += c;
        r += c;
    }
    cout << "! "<< l << '\n';
    return 0;
}