[Codeforces Round #516][Codeforces 1063C/1064E. Dwarves, Hats and Extrasensory Abilities]

题目链接：1063C - Dwarves, Hats and Extrasensory Abilities/1064E - Dwarves, Hats and Extrasensory Abilities

题目大意：交互题，每次询问一个点，返回该点的颜色（黑或白），在询问\(n\)次后求出一条直线，使得该直线可以将相同颜色的点分到一边，如果不存在这样的直线则判定为Wrong Answer。

　　　　　也就是说，询问的点要能保证，无论对方怎么回答，都能找到一条合法的直线满足条件。

题解：先引入两个概念：基准色 和 基准线。

　　　基准色，即询问的第一个点的颜色

　　　基准线，代表着下一次要询问基准线上的点，且基准线可以作为当前状态下的答案（在基准线左边的点的颜色与基准色相同，右边的颜色都与基准色不同）。基准线的一端为原点\((0,0)\)。

　　　每次询问时，若询问结果与基准色相同，则把基准线的另一端向右移动一段距离，否则向左移动。但是为了保证基准线的合法性，还需要确定这一段距离要取多长。

　　　由于\(n\)不超过30，考虑在\(2\)的次幂上做文章。假设当前还剩\(k\)个点未询问，则将\(2^k\)作为移动的距离。这样子就能保证无论怎么移动，基准线的移动都不会越过已经被询问过的点了。但是此时出现了一个问题，即最坏情况下，基准线的移动会不会超出题目的限制。可以发现，当所有点的颜色都与基准色相同时，移动的总距离为\(\sum_{i=0}^{n-1}2^i=2^n-1\)，当\(n\)为\(30\)时，有\(2^n-1=1073741823>10^9\)，超过了坐标的限制。因此当其超出范围时，需要将超出部分放在边界的右边。例如，当要询问的点为\((10^9+7,10^9)\)时，用\((10^9,10^9-7)\)来代替即可。

#include<bits/stdc++.h>

using namespace std;

int n,x,y,c,o=;

char s[];

int ask(int x)

{

    if(x>o)printf("%d %d\n",o,*o-x);

    else printf("%d %d\n",x,o);

    fflush(stdout);

    scanf("%s",s);

    return s[]=='b';

}

int main()

{

    scanf("%d",&n);

    c=ask();

    if(n==)return printf("0 0 %d %d\n",o,o),;

    n--;

    int cur=<<n;

    while(n)

      {

      int tmp=ask(cur);n--;

      if(tmp==c)cur+=<<n;

      else cur-=<<n;

      }

    printf("0 0 ");

    if(cur>o)printf("%d %d\n",o,*o-cur);

    else printf("%d %d\n",cur,o);

    return ;

}