Submission #6363153

---

Source Code Expand

test_mode = False #True
if test_mode:
    import random
    N = random.randint(1,10**9)
    print(N)

def ask(n):
    print('?', n)
    if not test_mode:
        ans = input().rstrip()
    else:
        ans = 'Y' if (n <= N and str(n) <= str(N)) or (n > N and str(n) > str(N)) else 'N'
    return ans == 'Y'

def solve():
    if ask(10**10):
        # power of 10
        for n in range(10,0,-1):
            if not ask(10 ** n - 1):
                return 10 ** n
        return 1
    # 以下10のべき乗以外
    d = 10
    while not ask(10 ** d):
        # 10 のべきを投げると、辞書順では自動で勝つ
        # よって、NO = n\leq 10^d
        d -= 1
    d += 1
    # Nはd桁
    left = 10 ** (d-1) # Nより小さい
    right = 10 ** d - 1 # N以上
    while right > left + 1:
        mid = (left + right) // 2
        if ask(mid * 10 ** 9):
            # 数字順では勝つ
            # 辞書順でmid >= NのときにTrue
            right = mid
        else:
            left = mid
    return right

answer = solve()
print('!', answer)

Submission Info

Judge Result