Codeforces Round #764 (Div. 3) F. Interacdive Problem (交互题、折半查找)

Codeforces Round #764 (Div. 3) F. Interacdive Problem (交互题、折半查找)

题目链接：https://codeforces.com/contest/1624/problem/F

题目大意
交互题，猜 1 1 1 到 n n n 中的一个数字 x x x。
每次 *** 作： + c + c +c，会使得 x = x + c x = x + c x=x+c，并返回 x / n ( 向 下 取 整 ) x / n(向下取整) x/n(向下取整) 的结果。

思路
二分 x 的取值范围，如何 c h e c k check check：
在第 i i i 次询问时，定义 s u m sum sum 表示前 i − 1 i-1 i−1 次询问中 c c c 的和， x x x 表示初始值， s x sx sx 表示当前认为初始 x x x 的值。
则 c = n − ( s u m + s x ) % n c = n - (sum + sx) % n c=n−(sum+sx)%n,

如果返回的结果大于等于 ( s u m + s x + c ) / n (sum + sx + c) / n (sum+sx+c)/n ，新的处置范围为 s x + 1 , r sx +1, r sx+1,r如果返回的结果小于 ( s u m + s x + c ) / n (sum + sx + c) / n (sum+sx+c)/n ，新的处置范围为 l , s x − 1 l, sx - 1 l,sx−1

ACcode

#include
#define ll long long
#define endl "n"
using namespace std;

const int maxn = 2e5 + 5;
const ll mod = 998244353;
const ll p = 233;

int check(int x){
	cout << "+ " << x << endl;
	int tmp;
	cin >> tmp;
	return tmp;
}
int main(){
	
	int n;
	cin >> n;
	
	int l = 1, r = n, res = -1;
	int sum = 0;
	while(l <= r){
		int sx = l + r >> 1; // 每次 x 的取值范围小一半
		int y = (sum + sx) % n;
		int c = n - y;
		int flag = (sum + sx + c) / n;
		int q = check(c); sum += c;
		if(q >= flag){
			res = sx;
			l = sx + 1;
		}
		else r = sx - 1;
	}
	
	cout << "! " << res + sum << endl;
	
	return 0;
}