题目概述

交互题，现在要猜一个数 $x$ ，可以询问 $x$ 是不是 $l\le x\le r$ ，但是每次询问完成后 $x$ 会移动一个到距离 $\le K$ 的点。如果一次询问 $(l,l)$ 时 $x=l$ ，则猜中了，在 $4500$ 次内猜中。

解题报告

假如上一次在 $[L,R]$ 之间，那么很明显可以这样：取 $mid={L+R\over 2}$ ，然后问 $(L,mid)$ ，如果问到了那么下一次的区间就是 $[L-K,mid+K]$ ，否则 $[mid+1-K,R+K]$ 。

但是……这样永远都停不下来啊？很明显如果 $x$ 在一个小范围内反复跳跃根本不可能刚好问到 $x$ 啊？

你随机我也随机，就是这么扯皮……如果 $R-L\le 4K$ 因为 $K$ 不大，那么就随机一个 $pos$ 问 $(pos,pos)$ ，如果没问到就 $[L-K,R+K]$ 继续做。

示例程序

第一发没过……随便改了个随机种子就过了……

#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long LL;

int K;LL n,L,R,now;

inline bool Ask(LL L,LL R){
    printf("%lld %lld\n",L,R);fflush(stdout);char s[5];scanf("%s",s);
    if (s[0]=='Y') return true;return false;
}
int main(){
    srand(759405);scanf("%lld%d",&n,&K);L=1;R=n;
    for (LL mid=L+(R-L>>1);;mid=L+(R-L>>1)){
        if (R-L<=(K<<2)) {now=rand()%(R-L+1)+L;if (Ask(now,now)) return 0;L-=K;R+=K;}
        else if (Ask(L,mid)) L-=K,R=mid+K; else L=mid+1-K,R+=K;if (L<1) L=1;if (R>n) R=n;
    }return 0;
}