Problem:
 Score : 500 points    Problem Statement This is an interactive task.  Let N be an odd number at least 3 .  There are N seats arranged in a circle.
The seats are numbered 0 through N-1 .
For each i ( 0 ≤ i ≤ N - 2 ), Seat i and Seat i + 1 are adjacent.
Also, Seat N - 1 and Seat 0 are adjacent.  Each seat is either vacant, or oppupied by a man or a woman.
However, no two adjacent seats are occupied by two people of the same sex.
It can be shown that there is at least one empty seat where N is an odd number at least 3 .  You are given N , but the states of the seats are not given.
Your objective is to correctly guess the ID number of any one of the empty seats.
To do so, you can repeatedly send the following query:   Choose an integer i ( 0 ≤ i ≤ N - 1 ). If Seat i is empty, the problem is solved. Otherwise, you are notified of the sex of the person in Seat i .   Guess the ID number of an empty seat by sending at most 20 queries.      Constraints  N is an odd number.  3 ≤ N ≤ 99  999       Input and Output First, N is given from Standard Input in the following format:  N   Then, you should send queries.
A query should be printed to Standart Output in the following format.
Print a newline at the end.  i   The response to the query is given from Standard Input in the following format:  s   Here, s is Vacant , Male or Female .
Each of these means that Seat i is empty, occupied by a man and occupied by a woman, respectively.      Notice  Flush Standard Output each time you print something. Failure to do so may result in TLE .  Immediately terminate the program when s is Vacant . Otherwise, the verdict is indeterminate.  The verdict is indeterminate if more than 20 queries or ill-formatted queries are sent.        Sample Input / Output 1  In this sample, N = 3 , and Seat 0 , 1 , 2 are occupied by a man, occupied by a woman and vacant, respectively.    Input Output    3  0  Male  1  Female  2  Vacant

Solution (Python):
def main():
    n = int(input())

    def q(i):
        print(i, )
        s = str(input())
        if s == 'Vacant':
            exit()
        else:
            return s

    x = q(n-1)
    x = q(0)

    def ok(m):
        if m == 0:
            return False
        else:
            if (m%2 == 0 and q(m) != x) or (m%2 == 1 and q(m) == x):
                return True
            else:
                return False

    l = 0
    r = n-1
    while l+1 < r:
        c = (l+r)//2
        if ok(c):
            r = c
        else:
            l = c

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())

    def q(i):
        print(i, )
        s = str(input())
        if s == 'Vacant':
            exit()
        else:
            return s

    x = q(n-1)
    x = q(0)

    def ok(m):
        if m == 0:
            return False
        else:
            if (m%2 == 0 and q(m) != x) or (m%2 == 1 and q(m) == x):
                return True
            else:
                return False

    l = 0
    r = n-1
    while l+1 < r:
        c = (l+r)//2
        if ok(c):
            r = c
        else:
            l = c

if __name__ == '__main__':
    main()

Solution (Python):
import sys
n = int(input())
print(0)
sys.stdout.flush()
l = 0
r = n+1
x = input()
if x == "Vacant":
  exit()
prv = 0
while True:
  m = (l+r)//2
  print(m)
  sys.stdout.flush()
  y = input()
  if y == "Vacant":
    break
  if (x == y) ^ (prv%2 == m%2) == 0:
    if prv>m:
      r = m
    else:
      l = m
  else:
    if prv>m:
      l = m
    else:
      r = m
  prv = m
  x = y

Solution (Python):
import sys

def q(i):
  print(i, flush=True)
  r = input()
  if r == 'Vacant':
    sys.exit()
  return r == 'Female'

n = int(input())

def go(a, b, ra):
  m = (a + b) // 2
  d = m - a + 1
  rm = q(m)
  if (ra == rm) == (d % 2 == 1):
    go(m, b, rm)
  else:
    go(a, m, ra)

ra = q(0)
rb = q(n - 1)
go(0, n - 1, ra)

Solution (Python):
import sys
n = int(input())
print(0)
s = input()
if s == "Vacant":
    sys.exit()
l = 0
r = n
ls = s
rs = s

def nibun(l, r, m, ls, rs, s):
    if ((m-l) % 2 == 0 and ls == s) or\
        ((m-l) % 2 == 1 and ls != s):
        return 1
    else:
        return 0

for ii in range(21):
    m = (l+r)//2
    print(m)
    s = input()
    if s == "Vacant":
        break
    if nibun(l, r, m, ls, rs, s) == 0:
        r = m
        rs = s
    else:
        l = m
        ls = s

Solution (Python):
import sys
n = int(input())
print(0)
s = input()
if s == "Vacant":
    sys.exit()
l = 0
r = n
ls = s
rs = s

def nibun(l, r, m, ls, rs, s):
    if ((m-l) % 2 == 0 and ls == s) or\
        ((m-l) % 2 == 1 and ls != s):
        return 1
    else:
        return 0

for ii in range(21):
    m = (l+r)//2
    print(m)
    s = input()
    if s == "Vacant":
        break
    if nibun(l, r, m, ls, rs, s) == 0:
        r = m
        rs = s
    else:
        l = m
        ls = s

Solution (Python):
import sys
n = int(input())
print(0, flush=True)
s = input()
if s == "Vacant":
    sys.exit()
l = 0
r = n
ls = s
rs = s

def nibun(l, r, m, ls, rs, s):
    if ((m-l) % 2 == 0 and ls == s) or\
        ((m-l) % 2 == 1 and ls != s):
        return 1
    else:
        return 0

for ii in range(21):
    m = (l+r)//2
    print(m, flush=True)
    s = input()
    if s == "Vacant":
        break
    if nibun(l, r, m, ls, rs, s) == 0:
        r = m
        rs = s
    else:
        l = m
        ls = s

Solution (Python):
import sys
def main():
    n = int(input())
    print("0")
    sys.stdout.flush()
    x = input().rstrip()
    if x == "Vacant":
        sys.exit()
    print(n//2)
    sys.stdout.flush()
    y = input().rstrip()
    if y == "Vacant":
        sys.exit()
    l, r= 0, 0
    z = ""
    if x == y:
        if n//2%2 == 1:
            l = 0
            r = n//2
            z = x
        else:
            l = n//2
            r = n
            z = y
    else:
        if n//2%2 == 1:
            l = n//2
            r = n
            z = y
        else:
            l = 0
            r = n//2
            z = x
    while True:
        p = (l+r)//2
        print(p)
        sys.stdout.flush()
        w = input().rstrip()
        if w == "Vacant":
            sys.exit()
        if z == w:
            if l%2 == p%2:
                l = p
            else:
                r = p
        else:
            if l%2 == p%2:
                r = p
            else:
                l = p
                z = w

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())

print(0)
start = input()
if start == 'Vacant':
    print(0)
    exit()
print(n-1)
last = input()
if last == 'Vacant':
    print(n-1)
    exit()
left_seat = start
right_seat = last
def binary_search(left, right):
    global left_seat
    global right_seat
    mid = (left+right) // 2
    print(mid)
    query = input()
    num = mid - left
    
    if query == 'Vacant':
        exit()
    if num % 2 == 0:
        if query == left_seat:
            left_seat = query
            binary_search(mid,right)
        else:
            binary_search(left,mid)
    else:
        if query == left_seat:
            binary_search(left,mid)
        else:
            left_seat = query
            binary_search(mid,right)
binary_search(0,n-1)

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def foo(i):
    print(i,flush=True)
    s = ins()
    a[i] = h[s]
    if h[s]==1:
        exit()

h = {'Vacant':1, 'Male':2, 'Female':3}
n = inn()
a = [0]*(n+1)
foo(0)
a[n] = a[0]
p = 0
q = n
while True:
    r = (p+q)//2
    foo(r)
    if a[r]==a[p] and (r-p)%2==1 or a[r]!=a[p] and (r-p)%2==0:
        q = r
    else:
        p = r

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def foo(i):
    print(i,flush=True)
    s = ins()
    a[i] = h[s]
    if h[s]==1:
        exit()

h = {'Vacant':1, 'Male':2, 'Female':3}
n = inn()
a = [0]*(n+1)
foo(0)
a[n] = a[0]
p = 0
q = n
while True:
    r = (p+q)//2
    foo(r)
    if a[r]==a[p] and (r-p)%2==1 or a[r]!=a[p] and (r-p)%2==0:
        q = r
    else:
        p = r

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def foo(i):
    print(i,flush=True)
    s = ins()
    a[i] = h[s]
    if h[s]==1:
        exit()

h = {'Vacant':1, 'Male':2, 'Female':3}
n = inn()
a = [0]*(n+1)
foo(0)
a[n] = a[0]
p = 0
q = n
cnt = 1
while q>p+1:
    r = (p+q)//2
    foo(r)
    cnt += 1
    if cnt >= 20:
        exit()
    if a[r]==a[p] and (r-p)%2==1 or a[r]!=a[p] and (r-p)%2==0:
        q = r
    else:
        p = r
        
    
print("err")

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    left = 0
    right = N
    print(left,flush=True)
    ls = input()
    if ls == "Vacant":
        exit()
        
    while right-left > 1:
        mid = (right+left)//2
        print(mid,flush=True)
        nls = input()
        if nls == "Vacant":
            exit()
        if nls == ls:
            if (mid-left)%2 == 0:
                left = mid
            else:
                right = mid
        else:
            if (mid-left)%2 == 1:
                left = mid
                ls = nls
            else:
                right = mid

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
left = 0
right = N
print(left, flush=True)
left_seat = input()
if left_seat == 'Vacant':
    exit()


while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    mid_seat = input()
    if mid_seat == 'Vacant':
        exit()
    if mid_seat == left_seat:
        if (mid - left) % 2 == 0:
            left = mid
        else:
            right = mid
    else:
        if (mid - left) % 2 == 1:
            left = mid
            left_seat = mid_seat
        else:
            right = mid

Solution (Python):
n = int(input())
scale = 2 ** 30
while scale >= n:
  scale //= 2

print(0)
z0 = input()
now = 0
while True:
  tmp = now + scale
  print(tmp%n)
  z1 = input()
  if z1 == 'Vacant':
    exit()
  if z1 == z0:
    now = tmp
  scale //= 2

Solution (Python):
import sys
def query(i):
    print(i)
    sys.stdout.flush()
    s=input()
    if s=="Vacant":
        exit()
    return s=="Male"

def main():
    N=int(input())
    al=ar=query(0)
    l,r=0,N
    while True:
        m=(l+r)//2
        am=query(m)
        if al==am and (m-l)%2==1 or al!=am and (m-l)%2==0:
            r,ar=m,am
        else:
            l,al=m,am

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())

def ask(n):
    print(n, flush=True)
    resp = input().rstrip()[0]
    if resp == 'V':
        exit()
    return resp

def condition(L,R,resp_L,resp_R):
    if (R-L)&1:
        return resp_L == resp_R
    else:
        return resp_L != resp_R

resp = ask(0)

L = 0
R = N
resp_L = resp
resp_R = resp
for _ in range(19):
    M = (L + R) // 2
    resp_M = ask(M)
    if condition(L,M,resp_L,resp_M):
        R,resp_R = M,resp_M
    else:
        L,resp_L = M,resp_M

Solution (Python):

import sys


N = int(input())
print(0)
s = input()

def judge(x):
    print(x)
    l = input()
    if l=='Vacant':
        sys.exit()
    if x%2 == 0:
        if l == s:
            return True
        else:
            return False
    else:
        if l==s:
            return False
        else:
            return True            
    


ok = 0
ng = N-1
while (abs(ok-ng)>1):
    mid = (ok+ng)//2
    if judge(mid):
        ok = mid
    else:
        ng = mid
        
print(N-1)
l = input()

Solution (Python):
def main():
    import sys
    N = int(input())
    left = 0
    right = N
    table = ["?"]*N
    print(left)
    sys.stdin.flush()
    le = input()
    if le == "Vacant":
        return
    table[left] = le

    for i in range(20):
        c = (left + right) // 2
        print(c)
        sys.stdin.flush()
        s = input()
        if s == "Vacant":
            return
        table[c] = s
        if (c - left) % 2 == 0 and table[left] == table[c]:
            left = c
        elif (c - left) % 2 == 1 and table[left] != table[c]:
            left = c
        else:
            right = c


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())

def f(n):
    print(n, flush = True)
    S = input()
    if S == 'Vacant':
        exit()
    return S

l = 0
r = N
S = f(l)
for i in range(20):
    mid = (l + r) // 2
    U = f(mid)
    len = mid - l + 1
    if (len % 2 == 0 and S != U) or (len % 2 and S == U):
        l = mid
        S = U
    else:
        r = mid

Solution (Python):
def query(i):
    print(i)
    return input()


n = int(input())
gender = query(0)
if gender == 'Vacant':
    exit()
l = 0
r = n
for _ in range(19):
    mid = (l + r) // 2
    res = query(mid)
    if res == 'Vacant':
        exit()
    cnt = mid - l + 1
    if (cnt % 2 == 0 and res == gender) or (cnt % 2 != 0 and res != gender):
        r = mid
    else:
        l = mid
        gender = res

Solution (Python):
import sys

def solve():
    N = int(input())
    print("0" + "\n", flush = True)
    a = input()
    if a == "Vacant": return 0
    elif a == "Male": basis = 0
    else: basis = 1
    low, high = 0, N
    Fin = {0}
    while high - low > 1:
        mid = (low + high) // 2
        Fin |= {mid}
        print(str(mid) + "\n", flush = True)
        a = input()
        if a == "Vacant": break
        else:
            b = (0 if a == "Male" else 1)
            expected = (basis if mid % 2 == 0 else (basis + 1) % 2)
            if b != expected:
                high = mid
            else:
                low = mid
    else:
        if low in Fin: print(str(high) + "\n", flush = True)
        else: print(str(low) + "\n", flush = True)
        a = input()

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
n = int(input())


l, r = 0, n

print(0, flush=True)
re = input()
if re=="Vacant": exit()

for i in range(19):
    mid = (l+r)//2
    print(mid, flush=True)
    tmp = input()
    if tmp=="Vacant": exit()

    p = abs(l-mid)%2

    if (re!=tmp and p) or (re==tmp and p-1):
        l = mid
        re = tmp
    else:
        if abs(l-mid) in [1, n-1]:
            l = mid
            re = tmp
        else: r = mid

Solution (Python):
N = int(input())

seat = [0] * (N + 1)


def ask(i):
    print(i)

    s = input()
    if s == "Vacant":
        exit()
    seat[i] = s
    return s


l, r = 0, N - 1
ask(0)
ask(N - 1)

for _ in range(18):
    m = (r + l) // 2
    res = ask(m)
    if res == seat[l]:
        if (m - l) % 2 == 0:  
            l = m
        else:
            r = m
    else:
        if (m - l) % 2 == 0:  
            r = m
        else:
            l = m

Solution (Python):
N = int(input().rstrip("\n"))

print(0)
left_s = input().rstrip("\n")
if left_s == "Vacant":
    exit()
print(N-1)
right_s = input().rstrip("\n")
if right_s == "Vacant":
    exit()

even = left_s
odd = "Male" if even == "Female" else "Female"

right = N-1
left = 0
while right - left > 1:
    mid = (right + left) // 2
    print(mid)
    s = input().rstrip("\n")

    if s == "Vacant":
        exit()
    
    if mid % 2 == 0:
        if even == s:
            left = mid
        else:
            right = mid
    else:
        if odd == s:
            left = mid
        else:
            right = mid

print(left)
s = input().rstrip("\n")
if s == "Vacant":
    exit()
print(right)
s = input().rstrip("\n")
if s == "Vacant":
    exit()

Solution (Python):
N = int(input())
def q(i):
    print(i)
    r = input()
    if r[0]=='V': exit()
    return (r[0]=='M') ^ i%2

X = q(0)
def is_ok(m):
    if m==N: return False
    return q(m)==X
ok = 0
ng = N
while ng-ok > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m

Solution (Python):
N = int(input())
mid = (N-1)//2

print(mid)
s = input()
if s == "Vacant":
    exit()
else:
    mid_state = s

print(0)
s = input()
if s == "Vacant":
    exit()
elif (mid % 2 == 0 and mid_state != s) or (mid % 2 != 0 and mid_state == s):
    l, r, l_state = 0, mid, s
else:
    l, r, l_state = mid, N, mid_state

while True:
    if (r - l) % 2 != 0:
        i = (r-l+1)//2 + l
    else:
        i = (r-l)//2 + l
    print(i)
    s = input()
    if s == "Vacant":
        exit()
    elif ((i-l) % 2 == 0 and l_state != s) or ((i-l) % 2 != 0 and l_state == s):
        r = i
    else:
        l, l_state = i, s

Solution (Python):
n=int(input())
def out(t):
  print(t,flush=True)
  s=input()
  if s=='Male':return 0
  elif s=='Female':return 1
  else:exit()
l=0
r=n
f=out(0)
while l+1!=r:
  m=(l+r)//2
  if (m+f)%2==out(m):l=m
  else:r=m

Solution (Python):
N = int(input())

s = [None] * N
l, c, r = 0, N//2, N-1

while True:
    for i in (l, c, r):
        if s[i] == None:
            print(i, flush=True)
            s[i] = input()
            if s[i] == 'Vacant':
                exit()
    if ((c-l)%2==0 and s[l]!=s[c]) or ((c-l)%2 and s[l]==s[c]):
        r = c
        c = (l + r) // 2
    else:
        l = c
        c = (l + r) // 2

Solution (Python):
N = int(input())

def ask(i):
    print(i, flush=True)
    s = input()
    if s == "Vacant":
        exit()
    return s

s = ask(0)

L = 0
R = N
s_L = s
s_R = s
for _ in range(19):
    M = (L+R)//2
    s_M = ask(M)
    if ((M-L)%2) ^ (s_L == s_M):
        L = M
        s_L = s_M
    else:
        R = M
        s_R = s_M

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    def ask(n):
        print(n)
        sys.stdout.flush()
        s = input().rstrip('\n')
        if s == 'Vacant':
            exit()
        elif s == 'Male':
            return 0
        else:
            return 1

    N = int(input())

    a0 = ask(0)
    ok = 0
    ng = N-1
    mid = ((ng//2)//2) * 2
    while ng - ok > 2:
        a = ask(mid)
        if a == a0:
            ok = mid
        else:
            ng = mid
        mid = (((ok//2)+(ng//2))//2)*2
    ask((ok+ng)//2)
    ask(N-1)


if __name__ == '__main__':
    main()

Solution (Python):
def func(l, r, same) -> int:
    """
    X(l,r)X -> same=True
    X(l,r)y -> same=False
    次の送信クエリ候補を返す
    """
    parity = (r - l + 1) % 2
    if parity ^ same:
        ret = (l + r) // 2
    else:
        ret = -1
    return ret


def main():
    n = int(input())

    seat = [''] * n

    print(0, flush=True)
    response = input()
    if response[0] == 'V':
        print(0)
        return
    seat[0] = response[0]

    l, r = 0, n
    x = func(l, r, same=True)
    for _ in range(19):
        print(x, flush=True)
        response = input()
        if response[0] == 'V':
            print(x)
            return
        seat[x] = response[0]

        res = func(l, x, seat[l] == seat[x])
        if res != -1:
            r = x
            x = res
            continue

        res = func(x, r, seat[x] == seat[r % n])
        if res != -1:
            l = x
            x = res


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
print(0, flush=True)
s0 = input()
if s0 == 'Vacant':
    exit()
l = 0
r = N-1

while r - l > 1:
    m = (l+r) // 2  
    print(m, flush=True)
    s = input()
    if s == 'Vacant':
        exit()
    if m % 2 == 1:  
        if s != s0:  
            l = m  
        else:  
            r = m  
    else:  
        if s != s0:  
            r = m  
        else:  
            l = m
print(r, flush=True)
sr = input()

Solution (Python):




N = int(input())



print(0, flush=True)  
s0 = input()
if s0 == "Vacant":
    exit()

l = 0  
r = N-1  
while r - l > 1:
    m = (l+r) // 2  
    print(m, flush=False)
    s = input()
    if s == 'Vacant':
        exit()
    if m % 2 == 1:
        if s != s0:
            l = m
        else:
            r = m
    else:
        if s != s0:
            r = m
        else:
            l = m
print(r, flush=True)
sr = input()

Solution (Python):
N=int(input())
print(N-1)
s=input()
if s=="Vacant":
    exit()
elif s=="Male":
    flag=1
else:
    flag=0
print(0)
s=input()
if s=="Vacant":
    exit()
elif s=="Male":
    flag=1
else:
    flag=0
st=0
end=N-1

while s!="Vacant":
    a=(end+st)//2
    print(a)
    s=input()
    if (a+flag*1)%2:
        if s=="Male":
            st=a
        else:
            end=a
    else:
        if s=="Female":
            st=a
        else:
            end=a

Solution (Python):
N=int(input())






print(0, flush=True)
s0=input()
if s0=='Vacant':
    exit()

l=0   
r=N-1 
while r-l>1:
    m=(l+r)//2
    print(m, flush=True)
    s=input()
    if s=='Vacant':
        exit()
    if m&1:
        if s!=s0:
            l=m
        else:
            r=m
    else:
        if s==s0:
            l=m
        else:
            r=m
print(r, flush=True)
sr=input()

Solution (Python):
n=int(input())
def out(i):
  print(i,flush=True)
  s=input()
  if s=="Male":return 0
  elif s=="Female":return 1
  else:exit()
f=out(0)
ng=0
ok=n
while ng+1!=ok:
  mid=(ng+ok)//2
  if (mid+f)%2==out(mid)%2:ng=mid
  else:ok=mid

Solution (Python):
N = int(input())
print(0)
res = input()
if res == "Vacant":
    exit(0)

print(N-1)
res2 = input()
if res2 == "Vacant":
    exit(0)
seat = [""]*N
seat[0] = res
seat[N-1] = res

first = 0
last = N-1

for i in range(18):
    ret = (first + last) // 2
    if ret == first:
        ret += 1
    print(ret)
    res = input()
    seat[ret] = res
    if res == "Vacant":
        exit(0)
    else:
        if (res == seat[first] and (ret - first) % 2 == 0) or (res != seat[first] and (ret - first) % 2 == 1):
            first = ret
        else:
            last = ret-1

Solution (Python):
import sys

N = int(input())

print("0")
sys.stdout.flush()
zero = input()
high = N - 1
low = 0
if zero != "Vacant":
    while True:
        mid = (high + low) // 2
        print(mid)
        sex = input()
        if sex == "Vacant":
            break
        if (mid % 2 == 0 and sex == zero) or (mid % 2 == 1 and sex != zero):
            low = mid + 1
            
        else:
            high = mid - 1

Solution (Python):
import bisect
def main():
    n = int(input())
    print(0)
    s = input()
    seat_dict = {"Male": 1, "Female": 2}
    if s == "Male":
        ls = [1, 2] * ((n - 1) // 2) + [1] * ((n -1) % 2)
    elif s == "Female":
        ls = [2, 1] * ((n - 1) // 2) + [2] * ((n - 1) % 2)
    else:
        return
    up = n - 1
    down = 0
    for i in range(20):
        mid = (up + down) // 2
        if mid == down:
            mid = up
        print(mid)
        s = input()
        if s == "Vacant":
            break
        _s = seat_dict[s]
        if _s == ls[mid]:
            down = mid
        else:
            up = mid

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline


def q(i):
    print(i, flush=True)
    s = input().strip()
    if s == "Vacant":
        exit()
    return s


def f(l, r, lc, rc):
    m = (l+r)//2
    mc = q(m)

    if ((m-l) % 2 and lc == mc) or ((m-l) % 2 == 0 and lc != mc):
        f(l, m, lc, mc)
    elif ((r-m) % 2 and mc == rc) or ((r-m) % 2 == 0 and mc != rc):
        f(m, r, mc, rc)


def main():
    N = int(input())
    lc = q(0)
    rc = q(N-1)
    f(0, N-1, lc, rc)


if __name__ == '__main__':
    main()

Solution (Python):

def chk(n,S):
    if S[n]=="":
        print(n,flush=True)
        temp=input()
        if temp=="Vacant":
            exit()
        else:
            S[n]=temp
            return S[n]
    else:return S[n]

def chk2(S1,S2):
    T1=chk(S1,S)
    T2=chk(S2,S)
    if (S2-S1)%2!=0:
        if T1==T2:
            return True
        else:
            return False
    elif (S2-S1)%2==0:
        if T1!=T2:
            return True
        else:
            return False

def chk3(S1,S2):
    chk(S1,S)
    chk(S2,S)
    Sm=(S1+S2)//2
    if chk2(S1,Sm):
        chk3(S1,Sm)
    else:
        chk3(Sm,S2)

N=int(input())

S=[""]*N

chk3(0,N-1)

Solution (Python):
N = int(input())
print(0)
res = input()
if res == "Vacant":
    exit(0)

print(N-1)
res2 = input()
if res2 == "Vacant":
    exit(0)
seat = [""]*N
seat[0] = res
seat[N-1] = res

first = 0
last = N-1

for i in range(18):
    ret = (first + last) // 2
    if ret == first:
        ret += 1
    print(ret)
    res = input()
    seat[ret] = res
    if res == "Vacant":
        exit(0)
    else:
        if (res == seat[first] and (ret - first) % 2 == 0) or (res != seat[first] and (ret - first) % 2 == 1):
            first = ret
        else:
            last = ret-1

Solution (Python):
n=int(input())

def out(x):
	print(x,flush=True)
	nxt=input()
	if nxt=="Vacant":
		exit()
	return nxt=="Male"

Lgen=out(0)
Rgen=out(n-1)

l,r=0,n-1
while True:
	m=(l+r)//2
	gen=out(m)
	if (m-l)%2==int(gen==Lgen):
		r=m
		Rgen=gen
	else:
		l=m
		Lgen=gen

Solution (Python):
n=int(input())

def output(x):
	print(x,flush=True)
	nxt=input()
	if nxt=="Vacant":
		exit()
	return nxt=="Male"

Lgen=output(0)
Rgen=output(n-1)

l=0
r=n-1
while True:
	m=(l+r)//2
	gen=output(m)
	if gen==Lgen:
		if (m-l)%2:
			r=m
			Rgen=gen
		else:
			l=m
			Lgen=gen
	else:
		if (m-l)%2:
			l=m
			Lgen=gen
		else:
			r=m
			Rgen=gen

Solution (Python):
N = int(input())

def ask(n):
    print(n, flush=True)
    response = input().rstrip()[0]
    if response == 'V':
        exit()
    return response

def condition(start, middle, r_start, r_middle):
    if (middle-start)&1:
        return r_start == r_middle
    else:
        return r_start != r_middle

start = 0
end = N
r_start = ask(0)

for _ in range(19):
    middle = (start + end) // 2
    r_middle = ask(middle)
    if condition(start, middle, r_start, r_middle):
        end = middle
    else:
        start = middle
        r_start = r_middle

Solution (Python):
N = int(input())

def ask(n):
    print(n, flush=True)
    resp = input().rstrip()[0]
    if resp == 'V':
        exit()
    return resp

def condition(L,R,resp_L,resp_R):
    if (R-L)&1:
        return resp_L == resp_R
    else:
        return resp_L != resp_R

resp = ask(0)

L = 0
R = N
resp_L = resp
resp_R = resp
for _ in range(19):
    M = (L + R) // 2
    resp_M = ask(M)
    if condition(L,M,resp_L,resp_M):
        R,resp_R = M,resp_M
    else:
        L,resp_L = M,resp_M

Solution (Python):
N = int(input())
lowid= 0
highid = N-1
print(0)
lowsex = input()
if lowsex=='Vacant':
    exit()
print(N-1)
highsex = input()
if highsex=='Vacant':
    exit()
while highid-lowid>1:
    midid = (lowid+highid)//2
    print(midid)
    midsex = input()
    if midsex=='Vacant':
        exit()
    if (midid-lowid)%2==1 and midsex==lowsex:
        highid = midid
        highsex = midsex
    elif (midid-lowid)%2==0 and midsex!=lowsex:
        highid = midid
        highsex = midsex
    else:
        lowid = midid
        lowsex = midsex

Solution (Python):
N = int(input())
print(0)
while True:
    x = input().strip()
    if x=="Vacant":break
    high = N
    low = 0
    while high-low>1:
        mid = (high+low)//2
        print(mid)
        y = input().strip()
        if x=="Vacant":break
        if (mid%2==0 and y==x) or (mid%2==1 and y!=x):
            low = mid
        else:
            high = mid

Solution (Python):
import sys
d={"Vacant":0, "Male":1, "Female":-1}

N=int(input())
M=[2 for _ in range(N+1)]
print(0, flush=True)
M[0]=d[input()]
M[N]=M[0]

def search(l,r):
    if r - l == 2:
        print(l+1)
        sys.exit()
    print((l+r)//2, flush=True)
    return d[input()]
l=0
r=N
while True:
    m=(r+l)//2
    M[m] = search(l,r)
    if M[m] == 0:
        print(m)
        sys.exit()
    if (m-l) % 2 == 0:
        if M[m] == M[l]:
            l=m
        else:
            r=m
    else:
        if M[m] == M[l]:
            r=m
        else:
            l=m

Solution (Python):
def ask(q):
    print(q, flush=True)
    inp = input()
    if inp == "Vacant":
        exit()
    return inp


n = int(input())

l = ask(0)
r = ask(n-1)
left = 0
right = n-1

for _ in range(18):
    mid = (right + left) // 2
    m = ask(mid)

    if l == m and (mid - left) % 2 == 1:
        right = mid
        r = m
    elif l != m and (mid - left) % 2 == 0:
        right = mid
        r = m
    else:
        left = mid
        l = m

Solution (Python):
def examC():
    N = I()
    print(0)
    q = input()
    if q=="Vacant":
        exit()
    left = 0; right = N - 1
    for _ in range(20):
        cur = (left + right) // 2
        print(cur)
        next = input()
        if next=="Vacant":
            exit()

        if (cur % 2 == 1 and next == q) or (cur % 2 == 0 and next != q):
            right = cur
        else:
            left = cur + 1

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N = int(sys.stdin.buffer.readline())

VACANT = 'Vacant'
FEMALE = 'Female'
MALE = 'Male'


def check(n):
    print(n, flush=True)
    s = sys.stdin.buffer.readline().decode().rstrip()
    if s == VACANT:
        exit()
    return s


l = 0
h = N
ls = check(l)
while abs(l - h) > 1:
    mid = (l + h) // 2
    ms = check(mid)
    if ((mid - l) % 2 == 0) == (ls == ms):
        l = mid
        ls = ms
    else:
        h = mid
check(h)
check(l)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n=inp()
    ok=0
    ng=n
    print(0)
    s=input()
    if s=='Vacant':
        return
    for _ in range(19):
        mid = (ok+ng)//2
        print(mid)
        ss=input()
        if ss=='Vacant':
            return
        elif (ss==s and (mid-ok)%2==1) or (ss!=s and (mid-ok)%2==0):
            ng = mid
        else:
            ok = mid
            s = ss


if __name__ == "__main__":
    main()