はまやんはまやんはまやん

hamayanhamayan's blog

Pakenのうさぎ [技術室奥プログラミングコンテスト#4 Day1 M]

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_m

解説

https://atcoder.jp/contests/tkppc4-1/submissions/6672077

インタラクティブ問題への取り組み方はそんなに多くない。
なので、順番に可能性を考えていくと解ける場合が多い。
二分探索で解いていこう。
うさぎになる左右最小の区間が分かれば、その両端が答えになる。
これは、左右どちらも二分探索していけば、答えられる。

int N;
//---------------------------------------------------------------------------------------------------
string ask(vector<int> A) {
    int k = A.size();

    printf("? %d", k);
    fore(a, A) printf(" %d", a + 1);
    printf("\n");

    fflush(stdout);

    string res; cin >> res;
    return res;
}
string ask(int L, int R) {
    vector<int> A;
    rep(i, L, R + 1) A.push_back(i);
    return ask(A);
}
void answer(int a, int b) {
    printf("! %d %d\n", a + 1, b + 1);
    fflush(stdout);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    int ok, ng;
    int ans1, ans2;

    ok = 0, ng = N - 1;
    while (ok + 1 != ng) {
        int md = (ok + ng) / 2;
        if (ask(md, N - 1) == "Rabbit") ok = md;
        else ng = md;
    }
    ans1 = ok;

    ng = 0, ok = N - 1;
    while (ng + 1 != ok) {
        int md = (ng + ok) / 2;
        if (ask(0, md) == "Rabbit") ok = md;
        else ng = md;
    }
    ans2 = ok;

    answer(ans1, ans2);
}