Yukicoder No.253 ロウソクの長さ

,

http://yukicoder.me/problems/687

このところ茶会でいずさんに負け続けている。

solution

$X$が小さいときに気を配りつつ、二分探索。

質問した回数$i$に対し$m-i$を聞くようにして二分探索。 ただし、最初の$1$回は$X \le 100$かどうか等を聞くようにする。 $\log{10^9} \lt 30$であるので普通に二分探索をすると$30$回ほど質問が必要となり、$X \le 30$のあたりの数を区別する質問をする前に$X = 0$に到達し詰むからである。

implementation

#!/usr/bin/env python3
import sys
def ask(y):
    print('?', y)
    sys.stdout.flush()
    return int(input())
def ans(y):
    print('!', y)
    sys.exit()

m = 100
p = ask(m)
if p == 1:
    l = m
    r = 10**9 # (l, r]
elif p == -1:
    l = 10-1
    r = m-1
else:
    ans(m)
for i in range(1,100):
    m = (l+r+1) // 2
    p = ask(m-i)
    if p == 1:
        l = m
    elif p == -1:
        r = m
    else:
        ans(m)