交互题。
有$k$个值域为$[1, n]$的数。
请在不超过$60$次询问内找出其中的两个数。
每次询问形式为1 x y
交互库会返回$|x - a| <= |y - b| ? "TAK" : "NIE"$
其中$a, b$分别是使得$|x - a|,|y - b|$最小的且存在于序列中的数。
若询问$x, x + 1$的结果为“TAK”,说明在$1, x$内一定有解。
我们可以不断这样二分下去。直到找到一个解。
再在$1, x - 1$和$x +1, N$中重复以上操作,找到另一组解。
#include<iostream>
using namespace std;
int N, K;
string Yes = "TAK";
int check(int x) {
if(x + 1 > N) return 1;
printf("1 %d %d\n", x, x + 1);
fflush(stdout);
string buf;
cin >> buf;
return buf == Yes ? 1 : 0;
}
int Query(int l, int r) {
int ans = -1;
while(l <= r) {
int mid = l + r >> 1;
if(check(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> N >> K;
int a1 = Query(1, N);
int a2 = Query(1, a1 - 1);
int a3 = Query(a1 + 1, N);
printf("2 %d %d", a1, a2 == -1 ? a3 : a2);
return 0;
}