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):
keta1=0
for i in range(1,12+1):
  print('?',10**(i-1),flush=True)
  ans=input()
  if ans=='Y':
    keta1=i
if keta1!=12:
  keta=keta1
else:
  keta=12
  for i in range(10,0,-1):
    print('?',2*10**(i-1),flush=True)
    ans=input()
    if ans=='Y':
      keta=i
l=10**(keta-1)-1
r=10**keta
while r-l!=1:
  mid=(l+r)//2
  print('?',mid*10,flush=True)
  ans=input()
  if ans=='Y':
    r=mid
  else:
    l=mid
print('!',r,flush=True)

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline



cnt = 0

def ask(n):
    print(f"? {n}")
    sys.stdout.flush()
    return input() == "Y"
"""

def ask(n):
    global cnt
    cnt += 1
    print(f"? {n}, cnt = {cnt}")
    if n <= N:
        return str(n) <= str(N)
    else:
        return str(n) > str(N)
"""


def ans(n):
    print(f"! {n}")
    sys.stdout.flush()


N = 901234567

ok = 10
ng = 1
while ok-ng > 1:
    mid = (ok+ng)//2
    if ask(mid*10**15-1): ok = mid
    else: ng = mid
    

v = top = ng 

for _ in range(9):
    ok = 10
    ng = 0
    while ok-ng > 1:
        mid = (ok+ng)//2
        
        r = 10*v+mid
        while r < 10**12: r *= 10
        r -= 1
        
        if ask(r): ok = mid
        else: ng = mid
        
    v = v*10+ng


        
while v%10==0:
    v //= 10




res = [ask(10**i) for i in range(10)]

if all(res):
    two = [ask(2*10**i) for i in range(10)]
    if all(two):
        ans(1)
    else:
        idx = two.index(True)
        ans(10**(idx))

else:
    idx = res.index(False) 
    while v < 10**(idx-1):
        v *= 10
    ans(v)

Solution (Python):
import sys

def query(N):
    n=str(N)
    print("?",n)
    sys.stdout.flush()
    a=input()
    return a=="Y"

count=0
L=-1
start=2
end=11
while end-start>1:
    test=(end+start)//2
    if not query("1"+"0"*(test-1)):
        end=test
    else:
        start=test
    count+=1
if not query("1"+"0"*(start-1)):
    L=start-1
elif not query("1"+"0"*(end-1)):
    L=end-1
else:
    start=1
    end=10
    while end-start>1:
        test=(end+start)//2
        if query("9"*test):
            end=test
        else:
            start=test
        count+=1
    if query("9"*start):
        L=start
    elif query("9"*end):
        L=end
    count+=2
count+=2


ans=""
first=True
while L>1:
    start=int(first)
    end=9
    while end-start>1:
        test=(end+start)//2
        if query(ans+str(test)):
            start=test
        else:
            end=test
        count+=1
    
    if query(ans+str(end)):
        ans+=str(end)
    else:
        ans+=str(start)
    count+=1
    first=False
    L-=1

start=int(first)
end=9
while end-start>1:
    test=(end+start)//2
    if query(ans+str(test)+"0"):
        end=test
    else:
        start=test
    count+=1
if query(ans+str(start)+"0"):
    ans+=str(start)
else:
    ans+=str(end)
count+=1

print("!",ans)

Solution (Python):
import sys


def query(num):
    
    print("?", num)
    sys.stdout.flush()

    
    res = input()
    return res

"""
def query(num):
    print(num)
    if num == "":
        num = "0"
    if int(num) <= N and num <= str(N):
        return "Y"
    if int(num) > N and num > str(N):
        return "Y"
    return "N"
"""

def solve():
    ans = ""
    while len(ans) < 20:
        if len(ans) == 0:
            
            min_lim = 1
        else:
            min_lim = 0
        ok = 10
        ng = min_lim
        if query((ans + str(min_lim) + 9 * "9")[:17]) == "Y":
            
            if query(ans + "2") == "N":
                ans += str(min_lim)
                continue
            
            if query("1" + len(ans) * "0") == "Y":
                ans += str(min_lim)
                print("!", ans)
                return
            else:
                print("!", ans)
                return
        
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if query((ans + str(mid) + 9 * "9")[:17]) == "Y":
                ok = mid
            else:
                ng = mid
        ans += str(abs(ok))

N = 1000000000
solve()

Solution (Python):
import sys
l = 10**10-1
r = 10**11-1
while True:
  x = (l+r)//2
  print("? "+str(x))
  sys.stdout.flush()
  res = input()
  if res == "Y":
    r = x
  else:
    l = x
  if l+1 == r:
    break
cand = r
ansls = []
while True:
  if cand%10 == 0:
    s = cand//10
    if 1 <= s <= 10**9:
      ansls.append(s)
    cand //= 10
  else:
    break
ansls = ansls[::-1]
ln = len(ansls)
flg = 0
if len(str(ansls[0]+1)) > len(str(ansls[0])):
  flg = 1
l = -1
r = ln-1
while l+1<r:
  x = (l+r)//2
  print("? "+str(ansls[x]+1))
  sys.stdout.flush()
  if input() == "Y":
    r = x
  else:
    l = x
if flg == 1 and r == 1:
  print("? "+str(ansls[0]+1))
  sys.stdout.flush()
  if input() == "Y":
    print("! "+str(ansls[1]))
    sys.stdout.flush()
  else:
    print("! "+str(ansls[0]))
    sys.stdout.flush()
else:
  print("! "+str(ansls[r]))
  sys.stdout.flush()

Solution (Python):
import sys

def inout(n):
    print("?", n)
    sys.stdout.flush()
    S = input()
    return S == "Y"

def main():
    Length = -1
    for l in range(11):
        if not inout(10**l):
            Length = l
            break
    if Length == -1:
        for l in range(11):
            if inout(2*10**l):
                print("!", 10**l)
                return
    tmp = ""
    for _ in range(Length):
        l = 0
        r = 10
        while r - l > 1:
            m = (r+l)//2
            if inout(int(tmp + str(m) + "0"*(Length - len(tmp)))):
                r = m
            else:
                l = m
        if len(tmp) == Length-1:
            if l == 0 and inout(int(tmp + "0"*2)):
                tmp += str(l)
            else:
                tmp += str(l+1)
        elif len(tmp) == 0 and l == 0:
            tmp += str(1)
        else:
            tmp += str(l)
    print("!", tmp)
    return


if __name__ == "__main__":
    main()

Solution (Python):
from sys import exit
print("? 999999999", flush=True)
if input() == "N":
	print("! 1000000000", flush=True)
	exit()

ans = ""
while len(ans) < 9:
	if len(ans) == 0:
		ok, ng = 9, 0
	else:
		ok, ng = 9, -1
	while abs(ok-ng) > 1:
		x = (ok+ng)//2
		print("? " + ans + str(x) + "9"*9, flush=True)
		if input() == "Y":
			ok = x
		else:
			ng = x
	ans += str(ok)

if ans == "100000000":
	while ans != "1":
		print("? " + "9"*(len(ans)-1), flush=True)
		if input() == "N":
			break
		else:
			ans = ans[:-1]
else:
	while ans[-1] == "0":
		print("? " + str(int(ans)-1), flush=True)
		if input() == "Y":
			break
		else:
			ans = ans[:-1]

print("! " + ans, flush=True)
exit()

Solution (Python):
import sys
input = sys.stdin.readline
flush = sys.stdout.flush
digit = [0] * 11
for i in range(11):
  print("?", pow(10, i))
  flush()
  s = input()[: -1]
  digit[i] = s == "Y"
d = 0
for i in range(11):
  if digit[i]:
    d = i

if d < 10:
  ok = pow(10, d)
  ng = pow(10, d + 1)
  while ng - ok > 1:
    m = (ok + ng) // 2
    print("?", m * 10)
    flush()
    s = input()[: -1]
    if s == "N": ok = m
    else: ng = m
  print("!", ok + 1)
  flush()
  exit(0)
else:
  res = 1
  for i in range(11):
    print("?", pow(10, i + 1) - 1)
    flush()
    s = input()[: -1]
    if s == "Y":
      res = pow(10, i)
      break
  print("!", res)
  flush()
  exit(0)

Solution (Python):
import sys
def put(x):
    
    
    print('?', x)
def get():
    
    
    return input() == 'Y'
for i in range(1, 12)[::-1]:
    put(10**(i-1))
    if get():
        m = i
        break
if m>=11:
    for i in range(1, m):
        put(10**i-1)
        if get():
            print('!', 10**(i-1))
            break
else:
    ng = 10**m
    ok = 10**(m-1)
    while(ng-ok>1):
        mid = (ok+ng)//2
        put(str(mid)+'0'*1)
        if not get():ok = mid
        else: ng = mid
    print('!', ok+1)

Solution (Python):
import sys
l = 10**10-1
r = 10**11-1
while True:
  x = (l+r)//2
  print("? "+str(x))
  sys.stdout.flush()
  res = input()
  if res == "Y":
    r = x
  else:
    l = x
  if l+1 == r:
    break
cand = r
ansls = []
while True:
  if cand%10 == 0:
    s = cand//10
    if 1 <= s <= 10**9:
      ansls.append(s)
    cand //= 10
  else:
    break
ansls = ansls[::-1]
ln = len(ansls)
flg = 0
if len(str(ansls[0]+1)) > len(str(ansls[0])):
  flg = 1
l = -1
r = ln-1
while l+1<r:
  x = (l+r)//2
  print("? "+str(ansls[x]+1))
  sys.stdout.flush()
  if input() == "Y":
    r = x
  else:
    l = x
if flg == 1 and r == 1:
  print("! "+str(ansls[l]))
  sys.stdout.flush()
else:
  print("! "+str(ansls[r]))
  sys.stdout.flush()

Solution (Python):

def ask(ns):

    N = 481939123 

    NS = str(N)

    
    ns = str(ns)
    n = int(ns)

    if (n <= N and ns <= NS) or (n > N and ns > NS):
        print ("Y")
        return "Y"
    else:
        print ("N")
        return "N"


import sys

mode = 0 

for i in range(1,11):

    print ("?"+ " " + str(10**i), flush=True)

    if mode == 0:
        ret = input()
    else:
        ret = ask(10**i)

    if ret == "N":

        l = 10**(i-1)
        r = 10**i - 1

        while r - l != 1:

            m = (r+l) // 2

            print ("?"+ " " + str(m) + "0" , flush=True )

            if mode == 0:
                ret = input()
            else:
                ret = ask(str(m) + "0")

            if ret == "N":
                l = m
            else:
                r = m

        print ("! " + str(r), flush=True )
        sys.exit()

for i in range(1,11):

    print ("? "+ str(10**i - 1), flush=True)

    if mode == 0:
        ret = input()
    else:
        ret = ask(10**i-1)

    if ret == "Y":

        print ("! " + str(10 ** (i-1)) , flush=True )

        sys.exit()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n = 10 ** 10
    print("?", n)
    
    
    if input() == "Y":
        
        
        n = 2
        while 1:
            print("?", n)
            if input() == "Y":
                print("!", n // 2)
                exit()
            n *= 10
    
    else:
        
        
        
        n = 10 ** 8
        while 1:
            print("?", n)
            if input() == "Y": break
            n //= 10
        
        
        
        
        
        l = n
        r = 10 * n
        while l + 1 < r:
            m = (l + r) // 2
            print("?", m * 10)
            if input() == "Y":
                r = m
            else:
                l = m
        print("!", r)

main()

Solution (Python):
print('?', 10**10)
if input() == 'Y':
    for nod in range(10):
        print('?', 10**nod+1)
        if input() == 'Y':
            break
    ans = 10**nod
else:
    for nod in range(1, 10):
        print('?', 10**nod)
        if input() == 'Y':
            continue
            nod -= 1
        break
    ok = 10**(nod-1)
    ng = 10**nod
    while abs(ok - ng) > 1:
        med = (ok + ng)//2
        print('?', med*10+1)
        if input() == 'N':
            ok = med
        else:
            ng = med
    ans = ok+1
print('!', ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
flush = sys.stdin.flush()

def solve():
    l = 0
    r = 17
    while r-l > 1:
        m = (l+r) >> 1
        M = 10**m
        print("?",M)
        flush
        ans = input()
        if ans == "Y":
            l = m
        else:
            r = m
    k = l
    A = 0
    for i in range(k+1)[::-1]:
        l = max(0,i-k+1)
        r = 10
        while r-l > 1:
            m = (l+r) >> 1
            M = (A+m*10**i)*10
            print("?",M)
            flush
            ans = input()
            if ans == "Y":
                r = m
            else:
                l = m
        A += l*10**i
    if A < 10**9:
        if A == 10000000:
            M = 10**9
            print("?",M)
            flush
            ans = input()
            if ans == "N":
                print("!",A+1)
                return
        else:
            print("!",A+1)
            return
    l = -1
    r = 9
    while r-l > 1:
        m = (l+r) >> 1
        M = 10**m+1
        print("?",M)
        flush
        ans = input()
        if ans == "Y":
            r = m
        else:
            l = m
    print("!",10**r)
    return
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def Q(n,N):
    n = int(n)
    if (n<=N and str(n)<=str(N)) or (n>N and str(n)>str(N)):
        return "Y"
    else:
        return "N"
    
    
def main():
    import sys
    
    ans = ""
 
    
    print("? "+"1"+"0"*10)
    sys.stdout.flush()
    A = input()
    if A=="Y":
        n = 1
        print("? "+"9"*n)
        sys.stdout.flush()
        A = input()
        while A == "N":
            n+=1
            print("? "+"9"*n)
            sys.stdout.flush()
            A = input()
        print("! "+str(10**(n-1)))
    else:
        l = 0
        r = 10
        S = [""]*11
        S[0] ="Y"
        S[10] ="N"
        while 1:
            m = (l+r)//2
            print("? "+str(10**m))
            sys.stdout.flush()
            A = input()
            if A=="Y":
                if S[m+1]=="N":
                    K = m+1
                    break
                S[m] = "Y"
                l = m
            else:
                if S[m-1]=="Y":
                    K = m
                    break
                S[m] = "N"
                r = m
                
        l = 1
        r = 9
        S = [""]*10
        S[9] ="Y"
        ashi = "9"*10
        print("? "+ans + str(1) + ashi)
        sys.stdout.flush()
        A = input()
        if A=="Y":
            ans += "1"
        else:
            S[1] = "N"
            while 1:
                m = (l+r)//2
                print("? "+ans + str(m) + ashi)
                sys.stdout.flush()
                A = input()
                if A=="Y":
                    if S[m-1]=="N":
                        ans += str(m)
                        break
                    S[m] = "Y"
                    r = m
                else:
                    if S[m+1]=="Y":
                        ans += str(m+1)
                        break
                    S[m] = "N"
                    l = m
            
        for i in range(K-1):
            ashi = "9"*(10-i)
            l = 0
            r = 9
            S = [""]*10
            S[9]= "Y"
            print("? " + ans + str(0) + ashi)
            sys.stdout.flush()
            A = input()
            if A=="Y":
                ans += "0"
            else:
                S[0] = "N"
                while 1:
                    m = (l+r)//2
                    print("? " + ans + str(m) + ashi)
                    sys.stdout.flush()
                    A = input()
                    if A=="Y":
                        if S[m-1]=="N":
                            ans += str(m)
                            break
                        S[m] = "Y"
                        r = m
                    else:
                        if S[m+1]=="Y":
                            ans += str(m+1)
                            break
                        S[m] = "N"
                        l = m
        print("! " + ans)
        
    
    
main()

Solution (Python):
test_mode = False 
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):
        
        for n in range(10,0,-1):
            if not ask(10 ** n - 1):
                return 10 ** n
        return 1
    
    d = 10
    while not ask(10 ** d):
        
        
        d -= 1
    d += 1
    
    left = 10 ** (d-1) 
    right = 10 ** d - 1 
    while right > left + 1:
        mid = (left + right) // 2
        if ask(mid * 10 ** 9):
            
            
            right = mid
        else:
            left = mid
    return right

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

Solution (Python):



def solve():
    lo = 1
    hi = 11
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        x = 10 ** (mid - 1)
        print('?', x)
        r = input()
        if r == 'Y':
            lo = mid
        else:
            hi = mid

    k = lo

    if hi == 11:
        lo = 0
        hi = 10
        while lo + 1 < hi:
            mid = (lo + hi) // 2
            x = 2 * 10 ** (mid - 1)
            print('?', x)
            r = input()
            if r == 'Y':
                hi = mid
            else:
                lo = mid
        k = hi

    lo = 10 ** (k - 1) - 1
    hi = 10 ** k - 1
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        x = 10 * mid
        print('?', x)
        r = input()
        if r == 'Y':
            hi = mid
        else:
            lo = mid

    return hi


def main():

    print('!', solve())

if __name__ == '__main__':
    main()

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

for dig in range(1, 12):
    print "? " + str(10 ** dig)
    sys.stdout.flush()
    rep = raw_input()
    if rep == "N":
        L = 10 ** (dig - 1)
        R = 10 ** dig - 1
        while R - L > 1:
            mid = (L + R) / 2
            print "? " + str(mid) + "00000"
            sys.stdout.flush()
            rep = raw_input()
            if rep == "Y":
                R = mid
            else:
                L = mid
        print "! " + str(R)
        exit()

for dig in range(1, 12):
    print "? " + str("9" * dig)
    sys.stdout.flush()
    rep = raw_input()
    if rep == "Y":
        print "! " + str(10 ** (dig - 1))
        exit()

Solution (Python):


def solve(SECRET = None):
  num_asks = 0
  def ask(n):
    n = int(n)
    nonlocal num_asks
    num_asks += 1
    assert 1 <= n <= int(1e18)
    if SECRET:
      return (n <= SECRET) == (str(n) <= str(SECRET))
    else:
      print("?", n)
      return input() == 'Y'

  if ask(100000000000):
    for k in range(1,19):
      if ask("9"*k):
        return 10**(k-1), num_asks
  else:
    for k in range(1,10):
      if not ask(10**k):
        
        low = 10**(k-1)
        high = (10**k) - 1
        ret = -1
        while low <= high:
          mid = (low + high) // 2
          if ask(str(mid) + "9"*k):
            ret = mid
            high = mid - 1
          else:
            low = mid + 1
        return ret, num_asks

  return -1, num_asks

ans, _ = solve()
print("!", ans)
exit(0)


import random
num_iter = 0
while True:
  num_iter += 1
  secret_len = random.randint(1, 9)
  SECRET = random.randrange(10**(secret_len-1),10**secret_len)
  ans, num_asks = solve(SECRET)
  assert num_asks <= 64
  if SECRET != ans or num_asks > 64:
    print(num_iter, "..", SECRET, ":", ans, num_asks)
    break
  if num_iter % 1000 == 0:
    print(num_iter)

Solution (Python):
import sys
def query(n):
	print "? %d"%n
	sys.stdout.flush()
	return raw_input()
i=1
while i<=1000000000 and query(i)=="Y":
	i*=10
if i==1000000000*10:
	while i!=0 and query(i+1)=="Y":
		i/=10
	print "! %d"%(i*10 if i!=0 else 1)
else:
	l=i/10
	r=i-1
	while l+1!=r:
		if query(((l+r)/2)*10)=="Y":
			r=(l+r)/2
		else:
			l=(l+r)/2
	print "! %d"%r

Solution (Python):
import sys
N = 0
debug = False
def test_init():
	N = int(input())
def test_eval(n):
	return ((n <= N and str(n) <= str(N)) or (n > N and str(n) > str(N)))

def query(n):
	
	if debug:
		return test_eval(n)
	print("? " + str(n))
	sys.stdout.flush()
	return input() == "Y"

def get_ndigit():
	retval = 1
	while not query(10 ** retval - 1):
		retval += 1
	if retval == 1:
		while not query((10 ** retval - 1) * 10 ** 9):
			retval += 1
		while not query(10 ** retval - 1):
			retval += 1
	return retval

def get_digit(x):
	l = len(str(x)) if x != 0 else 0
	def q(D):
		return query(x * 10 + D)
	d = 5
	r = q(d)
	if r:
		d = 7
		r = q(d)
		if r:
			d = 8
			r = q(d)
			if r:
				d = 9
				r = q(d)
				return 9 if r else 8
			else:
				return 7
		else:
			d = 6
			r = q(d)
			return 6 if r else 5
	else:
		d = 2
		r = q(d)
		if r:
			d = 3
			r = q(d)
			if r:
				d = 4
				r = q(d)
				return 4 if r else 3
			else:
				return 2
		else:
			d = 1
			r = q(d)
			return 1 if r else 0
if debug:
	test_init()
nd = get_ndigit()

value = 0
for i in range(nd - 1):
	value = value * 10 + get_digit(value)
ar = [False] * 10
i = 0
if nd == 1:
	i = 1
while not query((value * 10 + i) * 10):
	i += 1
value = value * 10 + i
print("! " + str(value))

Solution (Python):
for k in range(1,10):
    print('?',10**k,flush=True)
    if input()=='N':
        i=10**(k-1)+1
        j=10**k-1
        while i<j:
            m=(i+j)//2
            print('?',m*10,flush=True)
            if input()=='Y':
                j=m
            else:
                i=m+1
        print('!',i,flush=True)
        break
else:
    for k in range(10):
        print('?',10**(k+1)-1,flush=True)
        if input()=='Y':
            print('!',10**k,flush=True)
            break

Solution (Python):


import sys






























ans=None
for idx in range(0,11,1):
    print('? 1'+'0'*idx)
    sys.stdout.flush()
    kekka=input()
    if kekka=='N':
        digits=idx
        break
else:
    
    for idx in range(1,11,1):
        print('? '+'9'*idx)
        sys.stdout.flush()
        kekka=input()
        if kekka=='Y':
            c=idx-1
            break
    ans='! 1'+'0'*c

if ans==None:
    
    
    

    
    
    
    kagen=10**(digits-1) 
    jogen=10**(digits)-1 
    while jogen-kagen>1: 
        miru=(jogen+kagen)//2
        print('? '+str(miru)+'0')
        sys.stdout.flush()
        kekka=input()
        if kekka=='Y':
            jogen=miru
        else:
            kagen=miru

    ans='! '+str(jogen)
            

print(ans)

Solution (Python):
def query(val):
    print ('?', val)
    ans = input()
    if ans == 'Y':
        return True
    return False
LIMIT = 10 ** 9
import sys
if __name__ == "__main__":
    if (query(LIMIT)):
        res = 1
        while (True):
            if(query(2 * res)):
                print ('!', res)
                sys.exit()
            res *= 10
    digit = 10
    res = LIMIT
    while (True):
        if (query(res)):
            break
        res = res // 10
        digit -= 1
    query = 10 ** (digit)
    keta = 0
    while (keta < digit):
        low = query
        high = query * 10
        left = 0
        right = 10
        while (right - left > 1):
            med = (right + left) // 2
            if keta == 0 and med == 0:
                left = med
                continue
            val1 = list(str(low))
            val1[keta] = str(med)
            val1 = int("".join(val1))
            print ("? %d" %(val1))
            ans = input()
            if (ans == "Y"):
                if (keta == digit - 1):
                    query = val1
                right = med
                continue
            else:
                if (keta < digit - 1):
                    query = val1
                left = med
                continue
        keta += 1
    query = query // 10
    print ("! %d" % (query))

Solution (Python):
def query(val):
    print ('?', val)
    ans = input()
    if ans == 'Y':
        return True
    return False
LIMIT = 10 ** 9
import sys
if __name__ == "__main__":
    if (query(LIMIT)):
        res = 1
        while (True):
            if(query(2 * res)):
                print ('!', res)
                sys.exit()
            res *= 10
    digit = 10
    res = LIMIT
    while (True):
        if (query(res)):
            break
        res = res // 10
        digit -= 1
    query = 10 ** (digit)
    keta = 0
    while (keta < digit):
        low = query
        high = query * 10
        left = -1
        right = 10
        while (right - left > 1):
            med = (right + left) // 2
            if med < 0:
                left = med
                continue
            if med > 9:
                right = med
                continue
            if keta == 0 and med == 0:
                left = med
                continue
            val1 = list(str(low))
            val1[keta] = str(med)
            val1 = int("".join(val1))
            print ("? %d" %(val1))
            ans = input()
            if (ans == "Y"):
                if (keta == digit - 1):
                    query = val1
                right = med
                continue
            else:
                if (keta < digit - 1):
                    query = val1
                left = med
                continue
        keta += 1
    query = query // 10
    print ("! %d" % (query))

Solution (Python):
import sys





def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


debug = False
N = 5600070
if debug:
    print()
    print('N:', N)
    print()


def ask(n):
    if debug:
        res = (n <= N and str(n) <= str(N)) or (n >= N and str(n) >= str(N))
        print('?', n, '\t', res)
        return res
    print('?', n, flush=True)
    return input() in ['y', 'Y']


def solve():
    if ask(10 ** 9):
        
        for k in range(10):
            if ask(2 * 10 ** k):
                return 10 ** k

    
    l = 1
    while ask(10 ** l):
        l += 1

    d = [9] * l
    for p in range(l):

        a = 0
        if p == 0:
            a = 1
        b = 9

        d[p] = a
        n = int(''.join(map(str, d)))
        if ask(10 * n):
            continue

        while b - a > 1:
            m = (a + b) // 2
            d[p] = m
            n = int(''.join(map(str, d)))
            if ask(10 * n):
                b = m
            else:
                a = m
        d[p] = b
    n = int(''.join(map(str, d)))
    return n


def main():
    res = solve()
    print('!', res, flush=True)


if __name__ == '__main__':
    main()

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 = 188
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):
            answer(10**i)
            break
    exit(0)

left = 10**(dig-1); right = 10**dig
while left+1 < right:
    mid = (left + right) / 2
    if query(mid*10):
        right = mid
    else:
        left = mid

answer(right)

Solution (Python):



query = 10**9

print('? '+str(query))
res = input()


if res == 'Y':
    
    query *= 2
    
    for i in range(10):
        query = query // 10
        if query == 0:
            break
        print('? '+str(query))
        res = input()
        
        
        if res == 'N':
            break
    if query > 0:
        print('! '+str(query*5))
    else:
        print('! 1')
            
else:
    for i in range(9):
        query = query // 10
        
        print('? '+str(query))
        res = input()
        
        
        if res == 'Y':
            break
    
    
    
    
    
    min_N = query
    max_N = query*10 - 1
    cnt = 0
    
    while cnt < 100:
        query = (min_N + max_N) // 2
        if min_N + 1 >= max_N:
            print("! "+str(max_N))
            break
        
        print('? '+str(query*10))
        res = input()
        
        cnt += 1
        if res == 'N':
            min_N = query
        else:
            max_N = query

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())