题目链接:http://codeforces.com/contest/810/problem/D
题意:两个人玩一场游戏要猜出Noora选的f种菜的任意两种。一个人猜点另一个人回答 TAK如果 ,(x,y是猜的数,a表示Noora
选的菜中离x最近的,b是离y最近的,菜种是1~n个数。)否则就回答NIE。
题解:这题比较特殊,输入只需要n,k然后根据我们的输出题目作出反馈。
怎么确保能找到答案。我们可以将(1~n)分成两份(1~mid)(mid+1~r),显然要猜的数肯定是在这两个区间内。
然后怎么判断我们可以找mid和mid+1两个数来判断,如果|mid-a|<=|mid+1-b|,那么显然要猜的数肯定是mid或者mid
的左侧。如果|mid-a|>|mid+1-b|很显然要猜的数肯定是mid+1或者mid+1的右侧然后就是二分,根据题目的回答进行二分
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int n , k;
bool check(int x , int y) {
if(x < 0 || y > n) return false;
string res;
cout << 1 << ' ' << x << ' ' << y << endl;
cin >> res;
return res == "TAK";
}
int getnum(int l , int r) {
if(l > r) return -1;
int mid = (l + r) >> 1;
while(l < r) {
mid = (l + r) >> 1;
if(check(mid , mid + 1)) r = mid;
else l = mid + 1;
}
return l;
}
int main() {
cin >> n >> k;
int x , y;
x = getnum(1 , n);
y = getnum(1 , x - 1);
if(!check(y , x)) y = getnum(x + 1 , n);
cout << 2 << ' ' << x << ' ' << y << endl;
return 0;
}