Codeforces1624F. Interacdive Problem

传送门

题目大意

交互题，初始有一个数字 \(x(1\leq x ，每次可以进行询问 \(+\space c(1\leq c ，使得 \(x+=c\) ，并且给出 \(\lfloor\frac{x}{n}\rfloor\) 。
一开始输入一个 \(n(2< n\leq 1000)\) ,最多进行 \(10\) 次询问，最后求出 \(x\) 的值，输出 \(!\space x\) 。

思路

由于每次询问给出了 \(\lfloor\frac{x}{n}\rfloor\) 的值，我们只需要再知道 \(x\space mod\space n\) 的值即可，于是我们可以在进行二分，对于 \([lo,hi)\) 和 \(mid\) ，记录上一次询问得到的回答，我们每次询问 \(+ n-mid\) ，这样如果本次询问的回答 \(>\) 上一次的，说明在 \([mid,hi)\) 处，否则在 \([lo,mid)\) 处，我们将得到的新的 \(lo,hi\) 进行偏移，分别 \(+n-mid\) 之后 \(mod\space n\) 即可，如果 \(hi=0\) 那么设 \(hi=n\) 即可。
一开始区间为 \([0,n)\) ，上一次询问的回答为 \(0\) ，最后可以在 \(10\) 次以内求出答案。

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2+1
//#define rc p*2+2
//#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 100000000;
const LL mod = 998244353;
const int maxn = 100010;

int N;

void solve()
{
	int d, lst = 0;
	int lo = 0, hi = N;
	while (hi - lo > 1)
	{
		int mid = (hi + lo) / 2;
		cout << "+ " << N - mid << endl;
		cin >> d;
		if (d > lst)
			lo = mid;
		else
			hi = mid;
		lo = (lo + N - mid) % N;
		hi = (hi + N - mid) % N;
		if (hi == 0)
			hi = N;
		lst = d;
	}
	cout << "! " << lst * N + lo << endl;
}

int main()
{
	IOS;
	cin >> N;
	solve();

	return 0;
}