「Codeforces 1063C」Dwarves, Hats and Extrasensory Abilities

Description

题目链接:Codeforces 1063C

这是一道交互题。

给你一个正整数 $n$ 表示有 $n$ 个点。接下来你可以询问任意 $n$ 个点 $(x,y)$ 满足 $0\le x,y\le 10^9$,交互器会告诉你每个点的颜色是黑色还是白色。你需要确定一条直线,使得直线将所有的点分成两个部分,一部分的点都是白色,另一部分都是黑色。

数据范围:$1\le n\le 30$


Solution

由于是任意询问点,我们可以使所有的点都在一条直线上,左侧、右侧的点颜色不同。

首先询问点 $(0,y)$(这里的 $y$ 可以随意确定,只不过是保证点连成的直线和 $x$ 轴平行罢了),假设得到的颜色为白色,那么我们通过某种构造方法,使得左侧的点都是白色,右侧都是黑色。注意:接下来的分析都依次为根据!

定义搜索区间为最右侧的白点最左侧的黑点形成的区间(不包含两端)$[l,r]$。每次询问区间中点 $mid$,如果 $(mid,y)$ 的颜色为白色,那么搜索区间变为 $(mid,r]$ 否则为 $[l,mid)$。

这样我们最多可以询问 $\left\lfloor\log_2 10^9\right\rfloor=30$ 个点,刚好达到 $n$ 的上限。

画图可知,通过 $(l,0)$ 和 $(r,2)$ 的直线是满足要求的。(千万不要使用 $x=\left\lfloor\frac{l+r}{2}\right\rfloor$ 这条直线,在 $r-l\le 1$ 时会出错!)

时间复杂度:$O(n)$


Code

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

int ask(int x) {
printf("%d 1\n",x),fflush(stdout);
char s[10];
scanf("%s",s+1);
return s[1]=='w';
}
int main() {
int n;
scanf("%d",&n);
int col=ask(0);
int l=1,r=1e9;
for(int i=2;i<=n;++i) {
int mid=(l+r)>>1;
if(ask(mid)==col) l=mid+1;
else r=mid-1;
}
printf("%d 0 %d 2\n",l,r);
return 0;
}
0%