[NEERC2013]Interactive Interception

题目描述

题目传送门

思路

很好玩的交互题。

首先不难想到二分，可以二分位置。

因为询问比较的少，我们可以将每次二分后可能的位置记录下来，然后计算可能的速度。

不断逼近就可以得到答案。

询问次数是 $\log p$ 级别的。

代码

#include <bits/stdc++.h>
using namespace std;

string S;
bool Ask(int l, int r) {
	cout << "check " << l << " " << r << endl;
	cin >> S;
	return S[0] == 'Y'; 
}

int lp, rp, lv, rv, mid, t, L[100010], R[100010];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> rp >> rv;
	while (lp < rp) {
		mid = lp + rp >> 1;
		if (Ask(lp, mid))
			rp = mid;
		else
			lp = mid + 1;
		for (int i = 0; i < t; i++) {
			rv = min(rv, (rp - L[i]) / (t - i));
			lv = max(lv, (lp - R[i]) / (t - i));
		}
		L[t] = lp;
		R[t] = rp;
		lp += lv;
		rp += rv;
		t++;
	}
	cout << "answer " << lp << endl;
	return 0;	
}