交互题。
在 到 里有一个运动的点,要求找到这个点,每次可以查询一个区间内有没有这个点,每次这个点往左或者往右移动 到 个位置,要求要在 次查询内找到这个点的位置。
首先可以用二分缩小范围,但是不难发现长度最多只能缩小到 左右。
观察到 很小,所以考虑随机化,每次随机问一个位置,若不是就扩大区间,若区间长度超过 就重新二分。
由于 ,询问次数却有 次,所以找不到答案的概率几乎为 。
代码如下:
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
long long n;
int k;
char str[15];
inline bool que(long long l,long long r)
{
printf("%lld %lld\n",l,r);
fflush(stdout);
scanf("%s",str);
return str[0]=='Y';
}
int main()
{
srand(time(NULL));
scanf("%lld%d",&n,&k);
long long l=1,r=n;
while(l<r)
{
if(r-l+1<=k*4)
{
long long pos=l+1ll*rand()*rand()%(r-l+1);
if(que(pos,pos)) break;
l=max(l-k,1ll),r=min(r+k,n);
}
else
{
long long mid=l+r>>1;
if(que(l,mid)) r=min(mid+k,n),l=max(l-k,1ll);
else r=min(r+k,n),l=max(mid+1-k,1ll);
}
}
que(l,l);
return 0;
}