CF1039B Subway Pursuit 做题记录

交互题。

在 $1$ 到 $n$ 里有一个运动的点，要求找到这个点，每次可以查询一个区间内有没有这个点，每次这个点往左或者往右移动 $1$ 到 $k$ 个位置，要求要在 $4500$ 次查询内找到这个点的位置。

首先可以用二分缩小范围，但是不难发现长度最多只能缩小到 $4k$ 左右。

观察到 $k$ 很小，所以考虑随机化，每次随机问一个位置，若不是就扩大区间，若区间长度超过 $4k$ 就重新二分。

由于 $4k\le 40$，询问次数却有 $4500$ 次，所以找不到答案的概率几乎为 $0$。

代码如下：

#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;
}