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):
N = int(input())

print(0)
l = str(input())
if l == 'Vacant':
  exit()
print(N-1)
r = str(input())
if r == 'Vacant':
  exit()
  
left, right = 0, N-1
for i in range(20):
  n = (right+left) // 2
  print(n)
  a = str(input())
  if a == 'Vacant':
    exit()
  if (n-left) % 2 == 0:
    if l == a:
      left = n
    else:
      right = n
  else:
    if l == a:
      right = n
    else:
      left = n
      l = a

Solution (Python):
def apc001_c():
    import sys
    n = int(input())

    def ask(x:int):
        print(x)
        sys.stdout.flush()
        res = str(input())
        return res

    lower = 0
    seat_low = ask(lower)
    if seat_low == 'Vacant': return

    upper = n-1
    seat_up = ask(upper)
    if seat_up == 'Vacant': return

    while upper - lower > 1:
        x = (upper + lower) // 2
        s = ask(x)
        if s == 'Vacant': return
        if x % 2 == 0:
            if s == seat_low: lower = x
            else: upper = x
        else:
            if s == seat_up: lower = x
            else: upper = x

if __name__ == '__main__':
    apc001_c()

Solution (Python):
def solve():
    N = int(input())
    V = "Vacant"    
    M = "Male"
    F = "Female"

    l = 0
    r = N-1

    print(l)
    s = input()
    if s == V:
        return

    x = [F, F]
    x[s==F] = M
    
    while True:
        mid = (l+r+1)//2
        print(mid)
        s = input()
        if s == V:
            return
            
        if s == x[mid&1]:
            l = mid+1
        else:
            r = mid-1

solve()

Solution (Python):
import sys

N=int(input())
lo,hi = 0,N-1
print(lo,"\n")
sys.stdout.flush()
val_lo = input()
if val_lo == 'Vacant':exit()
print(hi,"\n")
sys.stdout.flush()
val_hi = input()
if val_hi == 'Vacant':exit()

while True:
  m = (lo+hi)//2
  print(m,"\n")
  sys.stdout.flush()
  val_m = input()
  if val_m == 'Vacant':exit()
  if ((m-lo) % 2 == 0 and val_lo != val_m) or ((m-lo) % 2 and val_lo == val_m):
    hi = m
    val_hi = val_m
  else:
    lo = m
    val_lo = val_m

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush


sys.setrecursionlimit(10**7)





from collections import deque



INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7
def intread():
    return int(sysread())
def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())


def get_ideal(s, target, s_val, N):
    dic = {'Male' : 0, 'Female' :1}
    rev = {0 : 'Male', 1: 'Female'}
    dist = min([abs(target - s), s + N - target, target + N - s])
    v = (dic[s_val] + (dist % 2)) % 2
    
    return rev[v]

def check(v):
    return True if v == 'Vacant' else False

from time import sleep
def query(x, L):
    print(x)
    
    
    
    v = input()
    
    L[x] = v
    if check(v):
        
        
        return True



def run():
    N = int(input())
    L = [''] * N
    check_lists = deque([])

    if query(0, L): return
    if query(N-1, L): return

    check_lists.append((0, N-1))
    while check_lists:
        
        a, b = check_lists.popleft()
        if abs(a-b) == 1:continue
        x = (a + b) // 2

        if query(x, L): return
        pred_a = get_ideal(a, x, L[a], N)
        pred_b = get_ideal(b, x, L[b], N)
        
        if pred_a == pred_b == L[x]:
            check_lists.append((a, x))
            check_lists.append((x, b))
        elif pred_a != L[x]:
            check_lists = deque([])
            check_lists.append((a, x))
        elif pred_b != L[x]:
            check_lists = deque([])
            check_lists.append((x, b))

if __name__ == "__main__":
    run()

Solution (Python):
n = int(input())
l, r = 0, n - 1
print(0)
data = input()
while data != "Vacant":
    m = (l + r) // 2
    print(m)
    s = input()
    if s == "Vacant":
        exit()
    if ( m % 2 == 0 and data == s) or ( m % 2 == 1 and data != s):
        l = m + 1
    else:
        r = m - 1

Solution (Python):
def check(i):
    print(i)
    c[i] = input()
    if c[i] == 'Vacant':
        exit(0)
n = int(input())
c = [-1]*n
l = 0
r = n-1
check(l)
check(r)
while True:
    m = (l+r)//2
    check(m)
    if (c[l] == c[m] and (m-l) % 2 != 0) or (c[l] != c[m] and (m-l) % 2 == 0):
        r = m
    else:
        l = m

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

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0
cnt = 1

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    cnt += 1
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid

print(high)
sys.stdout.flush()
s = input()
if s[0] == "V":
    exit()
else:
    print(low)
    sys.stdout.flush()
    s = input()
    exit()

Solution (Python):
import sys



def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def query(n: int):
    print(n, flush=True)
    res = input().rstrip()[0]
    if res == "V":
        sys.exit()
    return res


def main():
    n = input_int()
    record = [None] * n
    
    
    
    left = 0
    right = n - 1
    record[left] = query(left)
    record[right] = query(right)

    for i in range(18):
        mid = (left + right) // 2
        record[mid] = query(mid)
        if (mid - left) % 2 == 1:
            
            if record[left] == record[mid]:
                right = mid
            else:
                left = mid
        else:
            
            if record[left] == record[mid]:
                left = mid
            else:
                right = mid

    return


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
l = [-1] * N

def check(v):
    print(v)
    s = input()
    if s=="Male":
        l[v] = 0
    elif s=="Female":
        l[v] = 1
    else:
        exit(0)

check(0)
check(N-1)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2
    check(mid)
    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        right = mid
    else:
        left = mid

Solution (Python):
N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        right = mid
    else:
        left = mid

Solution (Python):
N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left, mid
    else:
        left, right = mid, right

Solution (Python):
import sys

n=int(input())

left=0
right=n-1

print(left)
sl=input()
if sl=="Vacant":
  sys.exit()
print(right)
sr=input()
if sr=="Vacant":
  sys.exit()


sm=""
while right-left>=2:
  mid=(left+right)//2
  print(mid)
  sm=input()
  if sm=="Vacant":
    sys.exit()
  if (sl==sm and (mid-left)%2==0) or (sl!=sm and (mid-left)%2==1):
    left=mid
    sl=sm
  else:
    right=mid
    sr=sm

print(left)
if input()=="Vacant":
  sys.exit()
print(right)
if input()=="Vacant":
  sys.exit()

Solution (Python):
def ask(n):
    
    l = ["Vacant", "Male", "Female"]
    
    
    
    print(n, flush=True)
    return l.index(input())


def resolve():
    N = int(input())
    sheets = [-1 for _ in range(N)]
    sheets[0] = ask(0)
    if sheets[0] == 0:
        return
    sheets[N - 1] = ask(N - 1)
    if sheets[N - 1] == 0:
        return
    ng = 0
    ok = N - 1
    mid = (ok + ng) // 2
    sheets[mid] = ask(mid)
    
    while sheets[mid] != 0:  
        mid = (ok + ng) // 2
        sheets[mid] = ask(mid)
        
        
        if ((mid - ng) % 2 and sheets[ng] == sheets[mid]) \
                or ((mid - ng + 1) % 2 and sheets[ng] != sheets[mid]):
            ok = mid
        else:
            ng = mid
    
    
    
    


resolve()

Solution (Python):
def query(q):
    print(q)
    a=input()
    if a=="Vacant":
        exit(0)
    return a

n=int(input())
d={}

a=query(0)
if a=="Male":
    d["Male"] = 1
    d["Female"] = 2
else:
    d["Male"] = 2
    d["Female"] = 1

a=query(n-2)
if d[a]==2:
    query(n-1)

M=n-2
m=0
while M-m>=2:
    x=(M+m+1)//2
    a=query(x)
    if (x+d[a])%2==1:
        m=x
    else:
        M=x

query(M)
query(m)

Solution (Python):
n=int(input())
print(0)
a=input()
d={}
if a=="Vacant":
    exit(0)
elif a=="Male":
    d["Male"] = 1
    d["Female"] = 2
else:
    d["Male"] = 2
    d["Female"] = 1
print(n-2)
a=input()
if a=="Vacant":
    exit(0)
elif d[a]==2:
    print(n-1)
    exit(0)

M=n-2
m=0

while M-m>=2:
    x=(M+m+1)//2

    print(x)
    a=input()
    if a=="Vacant":
        exit(0)

    if (x+d[a])%2==1:
        m=x
    else:
        M=x
        
    x=(M+m+1)//2

print(M)
a=input()
if a=="Vacant":
    exit(0)
print(m)
a=input()
if a=="Vacant":
    exit(0)

Solution (Python):
n = int(input())
h,e = 0,n-1
print(0)
g = input()

while g != 'Vacant':
    mid = (h+e)//2
    print(mid)
    s = input()
    if s=='Vacant':exit()
    if g==s and mid%2==0 or g!=s and mid%2==1:
        h = mid + 1
    else:
        e = mid - 1

Solution (Python):



n = int(input())


q = 0
print(q)
zero = input()

if zero == "Vacant":
    exit()

left = 1
right = n - 1


for _ in range(19):
    q = (left + right) // 2
    print(q)
    s = input()
    if s == "Vacant":
        exit()
    elif q % 2 == 0:
        if s == zero:
            left = q + 1
        else:
            right = q
    else:
        if s == zero:
            right = q
        else:
            left = q + 1

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


q = 0
print(q)
zero = input()

if zero == "Vacant":
    exit()

left = 1
right = n - 1

"""
0が男だったとする。

偶数(例えば10)が男だったら、
0, 1, ..., 10 = 男, 女, ..., 男　と並べることができる。
10, 11, ..., N-1(偶数) には空席がないと辻褄が合わない。

偶数(例えば10)が女だったら、
0, 1, ..., 10 には空席がないと辻褄が合わない。
10, 11, ..., N-1(偶数) = 女, 男, ..., 女 と並べることができる。

奇数(例えば11)が男だったら、
0, 1, ..., 11 には空席がないと辻褄が合わない。
11, 12, ...,N-1(偶数) = 男, 女, ..., 女 と並べることができる。

奇数(例えば11)が女だったら、
0, 1, ..., 11 = 男, 女, ..., 女　と並べることができる。
11, 12, ..., N-1(偶数) には空席がないと辻褄が合わない。
"""

for _ in range(19):
    q = (left + right) // 2
    print(q)
    s = input()
    if s == "Vacant":
        exit()
    elif q % 2 == 0:
        if s == zero:
            left = q + 1
        else:
            right = q
    else:
        if s == zero:
            right = q
        else:
            left = q + 1

Solution (Python):
n = int(input())
print(0)
st = input()
if st == "Vacant":
    exit()
print(n - 1)
en = input()
if en == "Vacant":
    exit()
l = 1
r = n - 1

while True:
    mid = (l + r) // 2
    print(mid)
    ask = input()
    if ask == "Vacant":
        exit()
    if (mid - l) & 1:
        if st == ask:
            l = mid + 1
            st = ask
        else:
            r = mid
            en = ask
    else:
        if st == ask:
            r = mid
            en = ask
        else:
            l = mid + 1
            st = ask

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

top = N - 1
lo = 0
while top - lo > 1:
    mid = (top + lo) // 2
    print(mid, flush=True)
    tmp = input()
    if tmp == 'Vacant':
        exit()
    elif ((mid - lo) % 2 != 0 and l == tmp) or ((mid - lo) % 2 == 0 and l != tmp):
        top = mid
    else:
        lo = mid
        l = tmp

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

top = N - 1
lo = 0
while True:
    mid = (top + lo) // 2
    print(mid, flush=True)
    tmp = input()
    if tmp == 'Vacant':
        exit()
    elif ((mid - lo) % 2 != 0 and l == tmp) or ((mid - lo) % 2 == 0 and l != tmp):
        top = mid
    else:
        lo = mid
        l = tmp

Solution (Python):
class Sender:

    def __init__(self):
        self.queue = {}
        self.dict = {
            "Vacant": 0,
            "Male": 1,
            "Female": 2
        }

    def send(self, x) -> bool:
        print(x, flush=True)
        self.queue[x] = self.dict[input()]
        return self.queue[x] == 0

    def compare(self, x, y) -> bool:
        return self.queue[x] == self.queue[y]


n = int(input())
s = Sender()

if s.send(0):
    exit()
if s.send(n - 1):
    exit()
l, r = 0, n-1
m = (n - 1) // 2
q = 2

while not s.send(m):
    q += 1
    if q == 20:
        break
    if ((r - m) % 2 == 0 and not s.compare(r, m)) or ((r - m) % 2 == 1 and s.compare(r, m)):
        l, r = m, r
        m = (r + m) // 2

    else:
        l, r = l, m
        m = (m + l) // 2

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def query(x):
        print(x)
        ret = input()
        if ret == "Vacant":
            sys.exit()
        return ret

    n = int(readline())

    l = 0
    r = n - 1

    op = {"Male": "Female", "Female": "Male"}

    ls = query(l)
    rs = query(r)

    while r - l > 1:
        mid = (l + r) // 2
        ms = query(mid)
        if (mid - l) % 2 == 0:
            if ls == ms:
                l = mid + 1
                ls = op[ms]
            else:
                r = mid - 1
                rs = op[ms]
        else:
            if ls == ms:
                r = mid - 1
                rs = op[ms]
            else:
                l = mid + 1
                ls = op[ms]
    query(l)
    query(r)


if __name__ == '__main__':
    main()

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    N = INT()

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

    ng = -1
    ok = N
    while True:
        mid = (ok + ng) // 2
        print(mid, flush=True)
        s = input()
        if s == 'Vacant':
            exit()

        if ( mid % 2 == 0 and s == s0 ) or ( mid % 2 == 1 and s != s0 ):
            ng = mid
        else:
            ok = mid

if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
q = lambda i:input('%d\n'%i)
i, j = 0, n - 1
a, b = q(i), q(j)
while True:
  k = (j - i + 1) // 2 + i
  c = q(k)
  if (k - i)%2 == (a==c):
    j = k
  else:
    a = c
    i = k

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    n = int(input())
    left = 0
    right = n - 1
    print(left)
    first = input()
    second = 'Male' if first == 'Female' else 'Female'
    p = 0
    while True:
        p = (left + right) // 2
        print(p)
        status = input()
        if status == 'Vacant':
            break
        if p % 2 == 0:
            if status == first:
                left = p + 1
            else:
                right = p
        else:
            if status == second:
                left = p + 1
            else:
                right = p


if __name__ == '__main__':
    main()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()

    ng = 0
    ok = N
    print(ng, flush=True)
    ng_s = SS()
    ok_s = ng_s
    while abs(ok-ng)>1:
        m = (ng+ok)//2
        print(m, flush=True)
        s = SS()
        if s == 'Vacant':
            sys.exit()
        elif (ok - m) % 2 == 1 and ok_s != s or (ok - m) % 2 == 0 and ok_s == s:
            ok = m
            ok_s = s
        else:
            ng = m
            ng_s = s

if __name__ == '__main__':
    resolve()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    print(0, flush=True)
    s = input().strip()
    if s == 'Vacant':
        return True
    ls, rs = s, s
    l, r = 0, N
    while True:
        m = (l + r) // 2
        print(m, flush=True)
        s = input().strip()
        if s == 'Vacant':
            return True
        if (m - l) % 2 == 0 and s != ls:
            r = m
            rs = s
        elif (m - l) % 2 == 1 and s == ls:
            r = m
            rs = s
        elif (r - m) % 2 == 0 and s != rs:
            l = m
            ls = s
        elif (r - m) % 2 == 1 and s == rs:
            l = m
            ls = s

if __name__ == '__main__':
    main()

Solution (Python):
from math import *
n=int(input())
mi,mx=0,n-1
print(mi)
t1=input()
if t1=="Vacant":
    exit()
print(mx)
t2=input()
if t2=="Vacant":
    exit()
while True:
    mid=ceil((mi+mx)/2)
    print(mid)
    t2=input()
    if t2=="Vacant":
        exit()
    sa=mid-mi
    if sa%2==0:
        if t1==t2:
            mi=mid
            t1=t2
        else:
            mx=mid
    else:
        if t1==t2:
            mx=mid
        else:
            mi=mid
            t1=t2

Solution (Python):
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def lcm(x, y):
    return (x * y) // math.gcd(x, y)
def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD
def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  
    fac = [0] * SIZE  
    finv = [0] * SIZE  
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    
    
    
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    
    return X.flatten().tolist()[0]

class TwoDimGrid:
    
    def __init__(self, h, w, wall="
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        
        
        
        
        
def fprint(c):
    print(c)
    sys.stdout.flush()
def solve():
    n = getN()
    fprint(0)
    res = getS()
    if res == "Vacant":
        return
    rc = res
    lc = res
    ln = 0
    rn = n
    
    q = 1
    while(True):
        if q > 21:
            return
        mid = (ln + rn) // 2
        if res == "Vacant":
            return
        fprint(mid)
        res = getS()
        if res == "Vacant":
            return
        if res == lc and (mid - ln - 1) % 2 == 0:
            rn = mid
            rc = res
            continue
        if res != lc and (mid - ln - 1) % 2 == 1:
            rn = mid
            rc = res
            continue
        if res == rc and (rn - mid - 1) % 2 == 0:
            ln = mid
            lc = res
            continue
        if res != rc and (rn - mid - 1) % 2 == 1:
            ln = mid
            lc = res
            continue
        q += 1
        
        
        
        
        



def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

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

q=0
print(q)
zero=input()

if zero=="Vacant":
    exit()

ll=1
rr=n-1

for _ in range(19):
    q=(ll+rr)//2
    print(q)
    s=input()
    if s=="Vacant":
        exit()
    elif q%2==0:
        if s==zero:
            ll=q+1
        else:
            rr=q
    else:
        if s==zero:
            rr=q
        else:
            ll=q+1

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

print(0, flush=True)
begin = input()

l, r = 0, N
while abs(r - l) > 1:
    mid = (l+r) // 2
    print(mid, flush=True)
    sol = input()
    if sol == "Vacant":
        l = mid
        break
    elif mid % 2 == 0:
        if sol != begin:
            r = mid
        else:
            l = mid
    else:
        if sol != begin:
            l = mid
        else:
            r = mid

print(l)

Solution (Python):

import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    g = {'Vacant':0, 'Male':1, 'Female':2}



    print(0,flush=True)
    sl = g[input()]
    if sl == 0:
        return

    print(N-1,flush=True)
    sr = g[input()]
    if sr == 0:
        return
    
    l = 0
    r = N-1
    while r-l>1:

        m = (l+r)//2
        print(m,flush=True)
        a = g[input()]
        if a == 0:
            return
        
        if (m-l) % 2 == 1:
            if sl == a:
                r = m
                sr = a
            else:
                l = m
                sl = a

        else:
            if a != sl:
                r = m
                sr = a
            else:
                l = m
                sl = a
        

    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def has_vacant(l, r, l_g, r_g):
    if l_g == r_g:
        if (r-l)%2 == 1:
            return True
    if l_g != r_g:
        if (r-l)%2 == 0:
            return True
    return False


def interact(l, r, l_g, r_g):
    m = (l+r)//2
    print(m)
    g = input()
    if g == 'Vacant':
        return
    if has_vacant(l, m, l_g, g):
        return interact(l, m, l_g, g)
    if has_vacant(m, r, g, r_g):
        return interact(m, r, g, r_g)


def solve():
    """
    0 1 2 3 4 5 6 7 8
    M       M     
    """
    N = read_int()
    l, r = 0, N-1
    print(l)
    l_g = input()
    if l_g == 'Vacant':
        return
    print(r)
    r_g = input()
    if r_g == 'Vacant':
        return
    interact(l, r, l_g, r_g)


if __name__ == '__main__':
    solve()

Solution (Python):
n=int(input())
print(n-1)
base=input()
def srh(n,t, str):
    print(((n - 1) // 2) + t)
    point = input()
    if point == 'Vacant':
        return
    if n % 4 == 1:
        if point == str:
            srh((n // 2) + 1, t, point)
        else:
            srh((n // 2) + 1, t + (n // 2), str)
    else:
        if point == str:
            srh(n // 2, t + (n // 2) + 1, str)
        else:
            if point == 'Male':
                srh(n // 2, t, 'Female')
            else:
                srh(n // 2, t, 'Male')
srh(n, 0, base)

Solution (Python):
n = int(input())
left = 0
right = n - 1
print(left)
first = input()
second = 'Male' if first == 'Female' else 'Female'
p = 0
while True:
    p = (left + right) // 2
    print(p)
    status = input()
    if status == 'Vacant':
        break
    if p % 2 == 0:
        if status == first:
            left = p + 1
        else:
            right = p
    else:
        if status == second:
            left = p + 1
        else:
            right = p

Solution (Python):
import sys

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

l = 0
r = N - 1

p = 0
print(p, flush=True)
first = sys.stdin.readline().strip()
if first == "Vacant":
    sys.exit()
if first == "Male":
    second = "Female"
else:
    second = "Male"

while True:
    p = (l + r) // 2
    print(p, flush=True)
    sex = sys.stdin.readline().strip()
    if sex == "Vacant":
        
        sys.exit()
    if p % 2 == 0:
        
        if sex == first:
            l = p + 1
        
        else:
            r = p
    else:
        if sex == second:
            l = p + 1
        else:
            r = p

Solution (Python):
import sys
def main():
  N = int(input())
  
  print(0, flush = True)
  s = str(input())
  if s == "Vacant":sys.exit()
  l = [0, s]
  
  print((N-1), flush = True)
  r =  [N-1, str(input())]
  if r[1] == "Vacant":sys.exit()
  
  while True:
    print((l[0] + r[0])//2, flush = True)
    c = [(l[0] + r[0])//2, str(input())]
    if c[1] == "Vacant":sys.exit()
    if ((c[0]-l[0])%2 == 1 and c[1] == l[1]) or (c[0]-l[0])%2 == 0 and c[1] != l[1]:
      r = c
    else:
      l = c
          
if __name__ == "__main__":
  main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N = INT()

l = 0
r = N
print(0, flush=True)
retl = input()
if retl == "Vacant": exit()

print(N-1, flush=True)
retr = input()
if retr == "Vacant": exit()

while 1:
	m = (l+r)//2
	print(m, flush=True)
	retm = input()
	if retm == "Vacant": exit()

	if (m-l)%2 == 0 and retm == retl or (m-l)%2 == 1 and retm != retl:
		l = m
		retl = retm
	else:
		r = m
		retr = retm

Solution (Python):
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

Solution (Python):
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)