有一个梗是这样的:
> There will be an i̶n̶t̶e̶r̶a̶c̶t̶i̶v̶e̶ binary search problem in the round.
所以看到交互题就去想二分吧(适用于99%的交互题)。
尽管说题目允许你选的点不在一条直线上,但是考虑到$log_2(10^9)\approx30$,在一条直线上二分即可。
具体来说,假设你最后左边全是白点,右边全是黑点,那么你只需要每次询问当前区间中间的点是什么颜色,如果是白色则把区间缩减为右半边,是黑色则缩减成左半边即可。
时间复杂度:$O(n)$
代码:
```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
char tmp[10];
int ask(int pos)
{
printf("%d %d\n",pos,1);
fflush(stdout);
scanf("%s",tmp);
return tmp[0]=='b';
}
int main()
{
scanf("%d",&n);
int l=0,r=1000000000,c1=ask(0);
for(int i=1;i<n;++i)
{
int mid=(l+r)>>1;
int now=ask(mid);
if(c1==now)
{
l=mid;
}
else
{
r=mid;
}
}
printf("%d %d %d %d\n",l,0,l+1,2);
}
```