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 +  > N) return ;

    printf("1 %d %d\n", x, x + );

    fflush(stdout);

    string buf;

    cin >> buf;

    return buf == Yes ?  : ;

}

int Query(int l, int r) {

    int ans = -;

    while(l <= r) {

        int mid = l + r >> ;

        if(check(mid)) r = mid - , ans = mid;

        else l = mid + ;

    }

    return ans;

}

int main() {

    ios::sync_with_stdio(false); cin.tie();

    cin >> N >> K;

    int a1 = Query(, N);

    int a2 = Query(, a1 - );

    int a3 = Query(a1 + , N);

    printf("2 %d %d", a1, a2 == - ? a3 : a2);

    return ;

}

巴特西

codeforces415D. Glad to see you!(交互)

题意

Sol

最新文章

热门文章