場所当てゲーム [Ritsumeikan University Competitive Programming Camp 2019 Day 1 D]

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day1/problems/D

前提知識

• インタラクティブ

解説

N≦10の場合は全て聞けば答えが求まるので、solve1で解く。
10＜Nのsolve2での解き方が問題である。
　
リアクティブ問題は微妙に方針が決まっている所があるので、制約から方針を考えてみる。
N≦200であるが、2^8=256なので、8bitに収まる情報になっている。
質問が10回までなので、2ビットを使って解きそうな感じがある。
　
0～7をビットの判別に使うことにする。
xのiビット目が1ならば、xとiの間に辺を張ることにする。
すると、0がnearならば、0ビット目は1であることが分かる。
同様に行っていくと、0～7までを質問すると、全てのビットの01が分かるので、答えが一意に定まる。
それを答える。

int N, K;
//---------------------------------------------------------------------------------------------------
string ask(int x) {
    printf("%d\n", x + 1);
    fflush(stdout);

    string s; cin >> s;
    return s;
}
//---------------------------------------------------------------------------------------------------
void solve1() {
    printf("0\n");
    fflush(stdout);

    rep(k, 0, K) rep(i, 0, N) if (ask(i) == "Yes") break;
}
void solve2() {
    vector<pair<int, int>> v;
    rep(i, 8, N) rep(d, 0, 8) if (i & (1 << d)) v.push_back({ d, i });
    int n = v.size();
    printf("%d\n", n);
    fore(p, v) printf("%d %d\n", p.first + 1, p.second + 1);

    rep(k, 0, K) {
        int ans = 0, ng = 1;
        rep(d, 0, 8) {
            string res = ask(d);

            if (res == "Yes") {
                ng = 0;
                break;
            }
            if (res == "Near") ans += 1 << d;
        }
        if (ng) ask(ans);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;

    if (N <= 10) solve1();
    else solve2();
}