053 - Discrete Dowsing（★7） https://atcoder.jp/contests/typical90/tasks/typical90_ba

typical90_ba.py

idx = [-1] * 1609
fib = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]

def ask(i):
    if idx[i] == -1:
        print("?", i)
        idx[i] = int(input())
    return idx[i]

def solv():
    N = int(input())
    ans = 0
    for i in range(N + 1):
        idx[i] = -1
    for i in range(N + 1, 1601):
        idx[i] = -i
    if N <= 5:
        for i in range(1, N+1):
            ans = max(ans, ask(i))
        print("!", ans)
        return
    cl, cr, dl, dr = 0, 1597, 610, 987
    el = ask(dl)
    er = ask(dr)
    ans = max(ans, el, er)
    if el < er:
        cl = dl
        dl = dr
        dr = -1
        el = er
        er = -1
    else:
        cr = dr
        dr = dl
        dl = -1
        er = el
        el = -1
    for i in range(12, -1, -1):
        if dl == -1:
            dl = cl + fib[i]
            el = ask(dl)
        elif dr == -1:
            dr = cr - fib[i]
            er = ask(dr)
        ans = max(ans, el, er)
        if el < er:
            cl = dl
            dl = dr
            dr = -1
            el = er
            er = -1
        else:
            cr = dr
            dr = dl
            dl = -1
            er = el
            el = -1
    for i in range(cl + 1, cr):
        ans = max(ans, ask(i))
    print("!", ans)
    return


T = int(input())
for _ in range(T):
    solv()