Codeforces 1011D Rocket

题面在这里

题意:交互题,猜一个数,会回答偏大偏小正确,但是有一个说谎序列,回答按照说谎序列循环,说谎回答完全相反,不超过60次询问

考虑到n很小,直接询问n次1,就知道说谎序列了

然后直接二分

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstdlib>

int n,m;
bool fake[50];
inline int ask(int x){
printf("%d\n",x);fflush(stdout);
scanf("%d",&x);return x;
}
int main(){
scanf("%d%d",&m,&n);
for (int i=1;i<=n;i++){
int x=ask(1); if (x==0) return 0;
fake[i]=(x<0);
}
int l=2,r=m,times=0;
while (l<=r){ times=times%n+1;
int mid=l+r>>1,x=ask(mid);
if (fake[times]) x=-x;
if (x==0) return 0;
if (x>0) l=mid+1;else r=mid-1;
}
return 0;
}