[NEERC2013]Interactive Interception

CmsMartin · 2022-08-26 14:42:58 · 题解

更好的阅读体验

题目描述

题目传送门

思路

很好玩的交互题。

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

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

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

询问次数是 \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;   
}