yukicoder No.253 ロウソクの長さ

インタラクティブ練習に。 二分探索はすぐわかるんですが、そこからが面白かったです。

writerの想定解とは違ったので書きました。（当初の想定解かな？）

考察

二分探索をとりあえずすると、小さい値の時、質問をしているうちに燃え尽きてしまうので詰みます。 これを回避する方法を考えることになります。

まず最初に二分探索のクエリを投げることを考えます。

そうすると、次はクエリに1を投げる必要があります。ここで聞かないと二度と1，2の判別ができなくなるからです。 その次には二分探索のクエリを奈が得ることができます。なぜなら、その次に1をクエリに投げることで、3，4の判別をする事が出来るからです。

ここからわかることは、1をクエリに投げることによって(その時の回数)と(その時の回数+1)を探索することができ、詰むまでに1回分の猶予が生まれるので、この間に二分探索のクエリをすればよいということです。

これを繰り返すと詰むことなく二分探索をする事が出来ます。

コード

int judge(int k) {
    cout << "? " << k << endl;
    return read();
}
void solve() {
    int ok = 1, ng = 1e9 + 1, mid;
    int times = 0;
    while (ng - ok > 1) {
        mid = (ok + ng) / 2;
        int num;
        if (mid - times >= 0) {
            num = judge(mid - times);
            if (num == 1) ok = mid;
            else if (num == 0) { ok = mid; break; }
            else ng = mid;
            times++;
        }
        num = judge(1);
        if (num == 0) {
            cout << "! " << times + 1 << endl;
            return;
        }
        else if (num == -1) {
            cout << "! " << times << endl;
            return;
        }
        times++;
    }
    cout << "! " << ok << endl;
}
signed main() {
    solve();
}