コンテンツにスキップ

ShareOJ - Truth or Lie

サイト
ShareOJ
問題
Truth or Lie

11 以上 NN 以下の秘密の整数 xx を当てるインタラクティブ問題です。

? l r と質問すると、xx が ll 以上 rr 以下かどうかが 11(はい)か 00(いいえ)で返ってきます。ただし、ジャッジは嘘つきかもしれません。嘘つきの場合は、常に逆の答えを返します。質問は 2020 回までで、N≤105N \le 10^5 です。

? 1 N と質問します。xx は必ず 11 以上 NN 以下なので、本当の答えは「はい」です。したがって、11 が返ってくればジャッジは正直者、00 が返ってくれば嘘つきだとわかります。

嘘つきなら、これ以降の応答をすべて反転すれば本当の答えになります。

あとは、ふつうの二分探索で xx を求めます。xx がありうる範囲を [l,r][l, r] として、真ん中 mm で区切り、xx が [l,m][l, m] にあるかを質問します。あれば r=mr = m、なければ l=m+1l = m + 1 とします。

範囲の大きさは 1 回ごとに半分(切り上げ)になるので、⌈log⁡2105⌉=17\lceil \log_2 10^5 \rceil = 17 回で 11 つに決まります。最初の 1 回と合わせて 1818 回なので、2020 回に収まります。

Python
N = int(input())
l = 1
r = N
print("?", 1, N, flush=True)
x = (int(input())) ^ 1
while l < r:
m = (l + r) // 2
print("?", l, m, flush=True)
res = int(input())
if res ^ x:
r = m
else:
l = m + 1
print("!", l, flush=True)

変数 x は秘密の整数ではなく、ジャッジが嘘つきなら 11、正直者なら 00 になるフラグです。res ^ x で応答を反転し、本当の答えに直しています。