原題鏈接：809B Glad to see you! (binary search, interactive, *2200)

題意簡述

交互題，長度為 的數(shù)列選中了 個位置，可以指定 詢問 到最近的選中的位置的距離是否小于等于 到最近的選中的位置的距離，需要在 次詢問內(nèi)得到任意兩個選中的位置。

解法分析

，詢問不超過 次，明示二分（事實(shí)上算法標(biāo)簽也是這樣）。

考慮在 中二分詢問 ，根據(jù)題意，當(dāng)?shù)玫娇隙ńY(jié)果 TAK 的時候，在左側(cè)必然有一個選中的位置，反之同理。

這樣二分的結(jié)果就是第一個位置 。

那么第二個位置怎么得到呢？繼續(xù)在 中二分顯然是不行的，將會得到相同的結(jié)果。不過我們可以嘗試在 中二分。但是如果第一次二分得到的 是最左側(cè)的選中的位置，在這個范圍內(nèi)沒有答案怎么辦呢？沒關(guān)系， 大約是 的三倍，我們還可以在 再次二分。

最后一個細(xì)節(jié)：怎么判斷在左側(cè)是否有解呢？如果二分的結(jié)果與第一次得到的 相等，顯然得到了一個假的（重復(fù)的）解，此時在左側(cè)無解。同時，因?yàn)? 是一個選中的位置，它的距離永遠(yuǎn)是 ，因此如果詢問 得到 NIE 就說明 的距離大于 ，即 不是一個解。

代碼

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
#define mulT0 int T; for(scanf("%d", &T);T;T--)
#define mulT1 int T, rnds; for(scanf("%d", &T),rnds=1;rnds<=T;rnds++)
using namespace std;
typedef long long ll;

int n, k, x, y;
bool interact(int x, int y) {
    printf("1 %d %d\n", x, y);
    fflush(stdout);
    char c[4];
    scanf("%s", c);
    return c[0] == 'T';
}
void give(int x, int y) {
    printf("2 %d %d\n", x, y);
    fflush(stdout);
}
int binarySearch(int l, int r) {
    while(l < r) {
        int mid = (l + r) >> 1;
        if(interact(mid, mid+1)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    scanf("%d%d", &n, &k);
    x = binarySearch(1, n);
    y = binarySearch(1, x-1);
    if(!(x ^ y) || !interact(y, x)) y = binarySearch(x+1, n);
    give(x, y);
    return 0;
}