「Codeforces 1063C」Dwarves, Hats and Extrasensory Abilities

发表于 | | 阅读次数:
字数统计: 484 字

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%