题目链接: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; }