名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

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