ShareOJ - Truth or Lie
- サイト
- ShareOJ
- 問題
- Truth or Lie
以上 以下の秘密の整数 を当てるインタラクティブ問題です。
? l r と質問すると、 が 以上 以下かどうかが (はい)か (いいえ)で返ってきます。ただし、ジャッジは嘘つきかもしれません。嘘つきの場合は、常に逆の答えを返します。質問は 回までで、 です。
嘘つきかどうかを先に調べる
Section titled “嘘つきかどうかを先に調べる”? 1 N と質問します。 は必ず 以上 以下なので、本当の答えは「はい」です。したがって、 が返ってくればジャッジは正直者、 が返ってくれば嘘つきだとわかります。
嘘つきなら、これ以降の応答をすべて反転すれば本当の答えになります。
あとは、ふつうの二分探索で を求めます。 がありうる範囲を として、真ん中 で区切り、 が にあるかを質問します。あれば 、なければ とします。
範囲の大きさは 1 回ごとに半分(切り上げ)になるので、 回で つに決まります。最初の 1 回と合わせて 回なので、 回に収まります。
Python
N = int(input())l = 1r = Nprint("?", 1, N, flush=True)x = (int(input())) ^ 1while l < r: m = (l + r) // 2 print("?", l, m, flush=True) res = int(input()) if res ^ x: r = m else: l = m + 1print("!", l, flush=True)変数 x は秘密の整数ではなく、ジャッジが嘘つきなら 、正直者なら になるフラグです。res ^ x で応答を反転し、本当の答えに直しています。