Problem:
 Score : 800 points    Problem Statement This is an interactive task.  Snuke has a favorite positive integer, N . You can ask him the following type of question at most 64 times: "Is n your favorite integer?" Identify N .  Snuke is twisted, and when asked "Is n your favorite integer?", he answers "Yes" if one of the two conditions below is satisfied, and answers "No" otherwise:   Both n \leq N and str(n) \leq str(N) hold.  Both n > N and str(n) > str(N) hold.   Here, str(x) is the decimal representation of x (without leading zeros) as a string. For example, str(123) =  123 and str(2000) = 2000 .
Strings are compared lexicographically. For example, 11111  <  123 and 123456789  <  9 .      Constraints  1 \leq N \leq 10^{9}       Input and Output Write your question to Standard Output in the following format:  ? n   Here, n must be an integer between 1 and 10^{18} (inclusive).  Then, the response to the question shall be given from Standard Input in the following format:  ans   Here, ans is either Y or N . Y represents "Yes"; N represents "No".  Finally, write your answer in the following format:  ! n   Here, n=N must hold.        Judging  After each output, you must flush Standard Output. Otherwise you may get TLE .  After you print the answer, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.  When your output is invalid or incorrect, the behavior of the judge is undefined (it does not necessarily give WA ).       Sample Below is a sample communication for the case N=123 :     Input  Output       ? 1    Y      ? 32    N      ? 1010    N      ? 999    Y      ! 123      Since 1 \leq 123 and str(1) \leq str(123) , the first response is "Yes".  Since 32 \leq 123 but str(32) > str(123) , the second response is "No".  Since 1010 > 123 but str(1010) \leq str(123) , the third response is "No".  Since 999 \geq 123 and str(999) > str(123) , the fourth response is "Yes".  The program successfully identifies N=123 in four questions, and thus passes the case.

Solution (Python):


def binsearch(l, r, pred): 
    assert l < r
    l -= 1
    while r - l > 1:
        m = (l + r) // 2
        if pred(m):
            r = m
        else:
            l = m
    return r

import sys
def pred(n):
    assert 1 <= n and n <= 10 ** 18
    print('?', n)
    sys.stdout.flush()
    return input() == 'Y'

def solve():
    s = ''
    s += str(binsearch(1, 9 + 1, lambda c: not pred(int(s + str(c)))) - 1)

    if s == '9':
        f = lambda k: pred(int('1' + '0' * k))
    else:
        f = lambda k: not pred(int('9' * k))
    k = 1
    while f(k):
        k += 1
        if k >= 13:
            return 1
    if k == 1:
        s = ''

    for _ in range(k - 2):
        s += str(binsearch(0, 9 + 1, lambda c: not pred(int(s + str(c)))) - 1)
    s += str(binsearch(0, 9 + 1, lambda c: pred(int(s + str(c) + '0'))))

    return int(s)

print('!', solve())

Solution (Python):


def solve():
    for i in range(1, 10):
        print("? {}".format(10**i))
        ans = input()
        if ans == "N":
            solve2(i)
            return
    solve1()

def solve2(i):
    '''10**(i-1) + 1 <= 10**i - 1 の範囲で解を求める。
    通常の二分探索で、末尾に0を付して探索していく。
    '''
    lower = 10**(i - 1)
    upper = 10**i - 1
    while (upper - lower > 1):
        mid = (lower + upper)//2
        print("? {}0".format(mid))
        ans = input()
        if ans == "Y":
            upper = mid
        else:
            lower = mid
    print("! {}".format(upper))

def solve1():
    '''1, 10, 100, ... 10**9 の中から正解を探す。
    '''
    for i in range(10):
        print("? {}".format(2 * 10**i))
        ans = input()
        if ans == "Y":
            print("! {}".format(10**i))
            return

solve()

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write
flush = sys.stdout.flush

def query(n):
    write("? %d\n" % n)
    flush()
    return readline().strip() == 'Y'
def answer(n):
    write("! %d\n" % n)
    flush()

"""
N = 123
q = 0
def dummy(n, N):
    return ((n <= N and str(n) <= str(N)) or (n > N and str(n) > str(N)))
def query(n):
    global q
    q += 1
    assert q <= 64
    print q, n, N, dummy(n, N)
    return dummy(n, N)
def answer(n):
    print "check", n, N
    assert n == N
"""

dig = None
for i in xrange(10):
    if not query(10**i):
        dig = i
        break
else:
    
    for i in xrange(10):
        if query(10**i+1):
            ans = 10**i
            break
    answer(ans)
    exit(0)

def check(ans, i):
    if i == dig-1:
        return not query(int("".join(map(str, ans)))*10)
    return query(int("".join(map(str, ans))))

ans = []
for i in xrange(dig):
    ans.append(0)
    left = (i<1)-1; right = 10
    while left+1 < right:
        mid = (left + right) / 2
        ans[i] = mid
        if check(ans, i):
            left = mid
        else:
            right = mid
    if i == dig-1:
        ans[i] = left+1
    else:
        ans[i] = left

num = int("".join(map(str, ans)))
answer(num)

Solution (Python):
import sys

test = False
N = 100

def check(n):
    if test:
        if n<=N and str(n)<=str(N) or n>N and str(n)>str(N):
            return "Y"
        else:
            return "N"
    else:
        print "?", n
        sys.stdout.flush()
        return raw_input()

for d in range(11):
    if check(10**d)=="N":
        d -= 1
        break
if d==10:
    for i in range(1,11):
        if check(10**i-1)=="Y":
            print "!", 10**(i-1)
            break
else:
    l = 10**d
    r = 10**(d+1)
    while r-l>1:
        m = (l+r)/2
        if check(m*10)=="Y":
            r = m
        else:
            l = m
    print "!", r
sys.stdout.flush()

Solution (Python):


def binsearch(l, r, pred): 
    assert l < r
    l -= 1
    while r - l > 1:
        m = (l + r) // 2
        if pred(m):
            r = m
        else:
            l = m
    return r

import sys
def pred(n):
    assert 1 <= n and n <= 10 ** 18
    print('?', n)
    sys.stdout.flush()
    return input() == 'Y'

def solve():
    s = ''
    s += str(binsearch(1, 9 + 1, lambda c: not pred(int(s + str(c)))) - 1)

    if s == '9':
        f = lambda k: pred(int('1' + '0' * k))
    else:
        f = lambda k: not pred(int('9' * k))
    k = 1
    while f(k):
        k += 1
        if k >= 13:
            return 1

    if k == 1:
        return binsearch(1, 9 + 1, lambda c: pred(int(str(c) + '0')))
    else:
        for _ in range(k - 2):
            s += str(binsearch(0, 9 + 1, lambda c: not pred(int(s + str(c)))) - 1)
        s += str(binsearch(0, 9 + 1, lambda c: pred(int(s + str(c) + '0'))))

    return int(s)

print('!', solve())