水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

No.246 質問と回答

回答

#37269 No.246 質問と回答 - yukicoder

問題文から二分探索だこれ! と思ったので,基本的には二分探索で実装.
ただ終了条件をどうするべきなのかわからなかったので,すでに訪れたところを再度調べる場合,これが答えるべき回答であると自分でテストしてみて気が付いた.なので,それを出力したら上手く行った.
サンプルがpythonだったけど,pythonで解いている人が少なくて悲しい^^;

import sys

res = -1
low, high = 1, 10 ** 9
check = []
for i in range(100):
    mid = (low + high) // 2
    if mid in check:
        print("!", mid)
        sys.stdout.flush()
        break
    check.append(mid)
    print("?", mid)
    sys.stdout.flush()
    res = int(input())
    if res == 1:
        low = mid
    else:
        high = mid