codeforces C - Dwarves, Hats and Extrasensory Abilities
这个交互式的题目非常巧妙
你给出一个点,他给你一种颜色,无论他给你什么颜色,你都可以找出一条线,能够把不同颜色的点分开
思路
如果两个点 颜色一样,那么第三个点必然不在两个点的中间,如果两个点颜色不一样,就把第三个点放在两个点的中间就好了
#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define ll long long
#define pb(i) push_back(i)
#define mp make_pair
using namespace std;
const int maxn=1e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
ll fpow(ll n, ll k, ll p = mod) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
ll inv(ll a, ll p = mod) {return fpow(a, p - 2, p);}
//head
int main()
{
ll n;
cin>>n;
cout<<100<<" "<<100<<endl;
string s,s2;
cin>>s;n--;
ll x=100;
while(n--)
{
cout<<x+(1ll<<(n))<< " "<<100<<endl;
cin>>s2;
if(s==s2) x = x+(1ll<<n);
}
cout<<x<<" "<<99<<" "<<x+1<<" "<<101<<endl;
return 0;
}