codeforces415D. Glad to see you!

題意

交互題。

有$k$個值域為$[1, n]$的數。

請在不超過$60$次詢問內找出其中的兩個數。

每次詢問形式為1 x y

交互庫會返回$|x - a| <= |y - b| ? "TAK" : "NIE"$

其中$a, b$分別是使得$|x - a|,|y - b|$最小的且存在於序列中的數。

Sol

若詢問$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;
}