这是一道交互题。
一共有 个人做成一圈,他们的编号从 到 。
现在每个人的手里面都有一个数字 ,并且保证每个人与他周围两个人的数字差为 ,即 ,特别地,编号为 与 的人也满足这个规则。
在这个圈里面,编号为 的人的对面坐着的是编号为 的人(其中 ),现在要你找到哪个人与他对面坐着的那个人手中的数字一样。
。
首先若 是奇数那么无解,因为 和 之间隔了 个 ,若 是奇数那么 和 奇偶性一定不同。
考虑 为偶数的情况,令 ,。显然问题转化成找到一个 的 ,满足 。那么观察到 都是偶数,所以 。也就是说,若 异号,则 中一定有至少一个 ,即 中一定有满足条件的位置。
由于 ,所以若 那么 中一定有至少一个满足条件的位置。那么在这个区间中二分即可,若 与 异号,那么往 二分,否则往 二分。
代码如下:
// Problem: CF1019B The hat
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1019B
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstdio>
using namespace std;
int n;
inline int que(int x)
{
printf("? %d\n",x);
fflush(stdout);
int res;
scanf("%d",&res);
return res;
}
int main()
{
scanf("%d",&n);
if(n%4!=0)
{
puts("! -1");
fflush(stdout);
return 0;
}
int l=1,r=n/2+1,ans=-1;
int d1=que(1)-que(1+n/2);
if(d1==0)
{
puts("! 1");
fflush(stdout);
return 0;
}
while(l<=r)
{
int mid=l+r>>1;
int di=que(mid)-que(mid+n/2);
if(di==0)
{
ans=mid;
break;
}
else if(di<0^d1<0) r=mid-1;
else l=mid+1;
}
printf("! %d\n",ans);
fflush(stdout);
return 0;
}