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 chk(i):
    print(i)
    return {'Vacant': 0, 'Male': 1, 'Female': -1}[input()]
N = int(input())
l = 0
r = N
sl = chk(l)
if sl:
    while True:
        m = (l+r)//2
        sm = chk(m)
        if sm == 0:
            break
        
        if (sl == sm and (l-m) % 2 == 0) or (sl != sm and (l-m) % 2 == 1):
            l = m
            sl = sm
        else:
            r = m

Solution (Python):
A=int(input())
print(0)
S=input()
if S=="Vacant":
    exit()

MAX=A
MIN=0
MID=(MAX+MIN)//2
for i in range(19):
    print(MID)
    s=input()
    if s=="Vacant":
        exit()
    elif MID%2==0:
        if S==s:
            MIN=MID
            MID=(MAX+MIN)//2
        else:
            MAX=MID
            MID=(MAX+MIN)//2
    else:
        if S!=s:
            MIN=MID
            MID=(MAX+MIN)//2
        else:
            MAX=MID
            MID=(MAX+MIN)//2

Solution (Python):

N = int(input())
print(0)
s = input()
if s=="Vacant":
    exit()
left=0
right=N
l_state = r_state = s
while True:
    center = (left+right)//2
    print(center)
    s = input()
    if s == "Vacant":
        exit()
    if ((center-left)%2) ^ (s!=l_state):
        right = center
        r_state = s
    else:
        left = center
        l_state = s

Solution (Python):
from collections import defaultdict as d
p=d(str)
n=int(input())
print(0, flush = True)
s = input()
if s == "Vacant": exit()
else:
    p[0]=s
    p[n]=s
    l=0
    r=n
    while 1:
        g=(l+r)//2
        print(g, flush = True)
        s = input()
        p[g]=s
        if s == "Vacant": break
        else:
            t=p[l]
            if ((g-l)%2!=0 and s!=t) or ((g-l)%2!=1 and s==t):
                l=g
            else:
                r=g

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

print(0, flush = True)
s = input()
if s == "Vacant": exit()
else:
    reference_state = s
    opposite_state = ("Male" if s == "Female" else "Female") 
    low, high = 0, N
    count = 1
    while count < 20:
        mid = (low + high)//2
        expected_state = (reference_state if mid % 2 == 0 else opposite_state)
        print(mid, flush = True)
        s = input()
        if s == "Vacant":
            break
        else:
            if s == expected_state: low = mid
            else: high = mid
            count += 1

Solution (Python):











import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    print 0
    sys.stdout.flush()

    input_raw = read_func().strip().split()
    s = (input_raw[0])
    if s == "Vacant":
        return
    zero = s

    print N - 1
    sys.stdout.flush()
    input_raw = read_func().strip().split()
    s = (input_raw[0])
    if s == "Vacant":
        return
    L = 0
    R = N - 1
    while 1:
        M = (R + L)/2
        if R - L == 2:
            print M
            sys.stdout.flush()
            input_raw = read_func().strip().split()
            s = (input_raw[0])
            if s == "Vacant":
                return

        if M % 2 == 1:
            M += 1

        print M
        sys.stdout.flush()
        input_raw = read_func().strip().split()
        s = (input_raw[0])
        if s == "Vacant":
            return
        if s == zero:
            L = M
        else:
            R = M


if __name__ == '__main__':
    main()

Solution (Python):


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians, log10
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul, xor
from copy import copy, deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits
from datetime import date

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()


print(0, flush=True)
s=input()
if s=='Male':
    even='Male'
    odd='Female'
elif s=='Female':
    even='Female'
    odd='Male'
else:
    exit()

def calc(q):
    print(q, flush=True)
    s=input()
    if s=='Vacant':
        exit()
    
    if q%2==0: 
        return s==even
    else: 
        return s==odd


hi=N-1
low=0
while low+1<hi:
    mid=(hi+low)//2
    if calc(mid):
        
        low=mid
    else:
        
        hi=mid
print(hi, flush=True)

Solution (Python):
N = int(input())
Info = [None] * 99999



print(0)
s = input()
Info[0] = s
if s == 'Vacant':
    exit()


print(N - 1)
s = input()
Info[N - 1] = s
if s == 'Vacant':
    exit()



l, r = 0, N - 1
while True:
    m = (l + r) // 2

    print(m)
    s = input()
    Info[m] = s
    if s == 'Vacant':
        exit()

    if (m - l) % 2 == 0:
        if Info[m] == Info[l]:
            l = m
        else:
            r = m

    else:
        if Info[m] == Info[l]:
            r = m
        else:
            l = m

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

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

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

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

Solution (Python):
n=int(input())
i=0
j=n-1
print(i)
a=input()
print(j)
b=input()
while 1:
    if j-i<2:
        print(i)
        _=input()
        print(j)
        if input()!='Vacant':
            print('助けてくれ～～～')
    k=(j-i)//2+i
    print(k)
    c=input()
    if(k-i)%2and a==c or not(k-i)%2and a!=c:
        j=k
    else:
        a=c
        i=k

Solution (Python):
n=int(input())
i=0
j=n-1
print(i)
a=input()
print(j)
b=input()
while 1:
    if j-i<2:
        print(i)
        _=input()
        print(j)
        if input()!='Vacant':
            print('助けてくれ～～～')
    k=(j-i)//2+i
    print(k)
    c=input()
    if(k-i)%2and a==c or not(k-i)%2and a!=c:
        j=k
    else:
        a=c
        i=k

Solution (Python):
import sys
n = int(input())
print(0)
s = input()
if s == "Vacant":
    sys.exit()
lb, ub = 0, n
ls, us = s, s
while True:
    mid = (lb + ub) // 2
    print(mid)
    mis = input()
    if mis == "Vacant":
        sys.exit()
    if (ls == mis) ^ ((mid - lb) & 1):
        lb = mid
        ls = mis
    else:
        ub = mid
        us = mis

Solution (Python):
from sys import exit

n = int(input())
print(0, flush=True)
inl = input()
inr = inl
if inl == "Vacant":
	exit()
print(n//2, flush=True)

inm = input()
if inm == "Vacant":
	exit()

outl, outr = 0, n

while True:
	
	if (((outl+outr)//2 - outl) % 2 == 0 and inl != inm) or (((outl+outr)//2 - outl) % 2 == 1 and inl == inm):
		outr = (outl+outr)//2
		print((outl+outr)//2, flush=True)
		inr = inm
		inm = input()
		if inm == "Vacant":
			exit()

	
	else:
		outl = (outl+outr)//2
		print((outl+outr)//2, flush=True)
		inl = inm
		inm = input()
		if inm == "Vacant":
			exit()

Solution (Python):
N=int(input())
print(0)
a=input()
m=-1
if a=="Vacant":
  exit()
elif a=="Male":
  m=0
elif a=="Female":
  m=1
l,r=1,N-1
while r-l>1:
  mid=(l+r)//2
  print(mid)
  a=input()
  if a=="Vacant":
    exit()
  elif a=="Male" and (mid-m)%2==0:
    l=mid
  elif a=="Female" and (mid-m)%2==1:
    l=mid
  else:
    r=mid
print(l)
if input()=="Vacant":
  exit()
print(r)
if input()=="Vacant":
  exit()

Solution (Python):
N=int(input())
print(0)
a=input()
m=-1
if a=="Vacant":
  exit()
elif a=="Male":
  m=0
elif a=="Female":
  m=1
l,r=1,N-1
while r-l>1:
  mid=(l+r)//2
  print(mid)
  a=input()
  if a=="Vacant":
    exit()
  elif a=="Male" and (mid-m)%2==0:
    l=mid
  elif a=="Female" and (mid-m)%2==1:
    l=mid
  else:
    r=mid
print(l)
if input()=="Vacant":
  exit()
print(r)
if input()=="Vacant":
  exit()

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

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def get_init(n: int):
    left = 0
    right = n-1
    dic = {}
    
    
    print(left, flush=True)
    s = ns()
    if s == 'Vacant':
        exit()
    elif s == 'Male':
        dic.update({0: 'Male'})
    else:
        dic.update({0: 'Female'})
        
        
    print(right, flush=True)
    s = ns()
    if s == 'Vacant':
        exit()
    elif s == 'Male':
        dic.update({1: 'Male'})
    else:
        dic.update({1: 'Female'})
        
    return dic

def search(n:int, dic: dict):
    left = 0
    right = n-1
    
    while right-left > 1:
        middle = (right+left)//2
        print(middle, flush=True)
        s = ns()
        if s == 'Vacant':
            exit()
        elif s == dic[middle%2]:
            left = middle
        else:
            right = middle
            
    print(left, flush=True)
    s = ns()
    if s == 'Vacant':
        exit()
        
    print(right, flush=True)
    s = ns()
    if s == 'Vacant':
        exit()
            

n = ni()

dic = get_init(n)
search(n, dic)

Solution (Python):
def nexts(X,Xs,Y,Ys):
    Z = (X+Y)//2
    print('{}\n'.format(Z))
    Zs = input()
    if Zs == 'Vacant':
        sys.exit()
    if (Xs == Zs and (Z-X)%2 == 1)\
    or (Xs != Zs and (Z-X)%2 == 0):
        Y, Ys = Z, Zs
    else:
        X, Xs = Z, Zs
    return X,Xs,Y,Ys

import sys

N = int(input())
print('0\n')
xs = input()
if xs == 'Vacant':
    sys.exit()
print('{}\n'.format(N-1))
ys = input()
if ys == 'Vacant':
    sys.exit()
x, y = 0, N-1
while True:
    x,xs,y,ys = nexts(x,xs,y,ys)

Solution (Python):
N = int( input())
V = [0]*(N+1)
L = 0
R = N
print(0)
s = input()
if s == "Vacant":
    pass
else:
    V[0] = V[N]= s
    for i in range(19):
        M = (L+R)//2
        print(M)
        s = input()
        if s == "Vacant":
            break
        else:
            V[M] = s
            if V[L] == V[M]:
                if (M-L)%2 == 1:
                    R = M
                else:
                    L = M
            else:
                if (M-L)%2 == 0:
                    R = M
                else:
                    L = M

Solution (Python):
N = int(input())
print(0, flush=True)
s = input()
if s == 'Vacant':
    exit()
l, r = 0, N
while True:
    mid = (l + r) // 2
    print(mid, flush=True)
    t = input()
    if s == 'Vacant':
        break
    
    if mid % 2:
        if s != t:
            l = mid
        else:
            r = mid
    else:
        if s == t:
            l = mid
        else:
            r = mid

Solution (Python):
from sys import stdout,exit
n = int(input())
print(0)
stdout.flush()
a = input()
if a=="Vacant": exit()
else: l = 0
print(n-1)
stdout.flush()
b = input()
if b=="Vacant": exit()
else: r = n-1
while True:
	m = (l+r)//2
	print(m)
	stdout.flush()
	c = input()
	if c=="Vacant": break
	elif (a!=c)^((m-l)%2): r = m
	else: l,a = m,c
exit()

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = inp()

def query(x):
	print(x)
	sex = input()
	if sex == 'Male':
		return True
	elif sex == 'Female':
		return False
	else:
		print(x)
		sys.exit()


l,r = 0,N
ls = rs = query(0)

while True:
	mid = (l+r)//2
	ms = query(mid)

	if (mid-l+1)%2 == 1 and ls != ms:
		r = mid
		rs = ms
	elif (mid-l+1)%2 == 0 and ls == ms:
		r = mid
		rs = ms
	elif (r-mid+1)%2 == 1 and rs != ms:
		l = mid
		ls = ms
	elif (r-mid+1)%2 == 0 and rs == ms:
		l = mid
		ls = ms

Solution (Python):
n = int(input())
print(0, flush=True)
syo = 0
s = input()
if s == "Vacant":
  exit()
syos = s
dai = n-1
print(n-1, flush=True)
s = input()
dais = s
if s == "Vacant":
  exit()
for _ in range(18):
  mid = (dai+syo)//2
  print(mid, flush=True)
  s = input()
  if s == "Vacant":
    exit()
  if ((mid - syo)%2 == 0 and s != syos) or ((mid - syo)%2 == 1 and s == syos):
    dai = mid
    dais = s
  else:
    syo = mid
    syos = s

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

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

ri = N - 1
print(ri, flush=True)
rs = input()
if rs == 'Vacant':
    exit()

for _ in range(18):
    mid = (li + ri) // 2

    print(mid, flush=True)
    s = input()

    if s == 'Vacant':
        exit()

    
    c1 = (mid - li) % 2 == 1 and ls == s
    c2 = (mid - li) % 2 == 0 and ls != s
    if c1 or c2:
        ri = mid
        rs = s
    else:
        li = mid
        ls = s

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

def q(n):
    print(n, flush=True)
    ans = input()
    if ans == 'Vacant': quit()
    return ans

def f():
    lb = 0
    ub = N
    lba = q(lb)
    while ub - lb > 1:
        qry = (lb + ub) // 2
        qa = q(qry)
        if (not ((lb ^ qry) & 1) and lba == qa) or (((lb ^ qry) & 1) and lba != qa):
            lb = qry
            lba = qa
        else:
            ub = qry
f()

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

def f():
    lb = 0
    ub = N - 1
    
    print(lb, flush=True)
    lba = input()
    if lba == 'Vacant': return
    
    print(ub, flush=True)
    uba = input()
    if uba == 'Vacant': return
    
    while lb < ub:
        qry = (lb + ub) // 2
        print(qry, flush=True)
        qa = input()
        if qa == 'Vacant': return
        if (not ((lb ^ qry) & 1) and lba == qa) or (((lb ^ qry) & 1) and lba != qa):
            lb = qry
            lba = qa
        else:
            ub = qry

f()

Solution (Python):
import sys

def q(i):
  print i
  sys.stdout.flush()
  s = raw_input()
  if s=="Vacant":
    sys.exit(0)
  else:
    return 0 if s=="Male" else 1

N, = map(int, raw_input().split())
S = [None]*N
l = 0
S[l] = q(l)
r = N-1
S[r] = q(r)
while True:
  m = (l+r)//2
  S[m] = q(m)
  if (m-l+S[m]-S[l])%2==0:
    l = m
  else:
    r = m

Solution (Python):
import sys
def g(i):
  print i
  sys.stdout.flush()
  s = raw_input()
  if s=="Vacant":
    sys.exit(0)
  return 0 if s=="Male" else 1

N = int(raw_input())
S = [0]*N
l = 0
S[l] = g(l)
r = N-1
S[r] = g(r)
while True:
  c=(r+l)//2
  S[c]=g(c)
  if (c-l)%2==(S[c]+S[l])%2:
    l=c
  else:
    r=c

Solution (Python):
import sys

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

def main():
    print(0)
    sys.stdout.flush()
    r = sys.stdin.readline().strip()
    if r == 'Vacant':
        return
    if r == 'Male':
        t = ['Male', 'Female']
    else:
        t = ['Female', 'Male']
    left = 1
    right = N - 1

    while True:
        pos = (left + right) // 2
        print(pos)
        sys.stdout.flush()
        r = sys.stdin.readline().strip()
        if r == 'Vacant':
            return
        if t[pos % 2] == r:
            left = pos + 1
        else:
            right = pos - 1

main()

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

def _input():
    s = input()
    if s == 'Vacant':
        sys.exit(0)
    return s


def check(x, y):
    
    if x[1] == y[1]:
        if x[0] % 2 == y[0] % 2:
            return True
        else:
            return False
    else:
        if x[0] % 2 == y[0] % 2:
            return False
        else:
            return True

print(0, flush=True)
s = _input()
left = (0, s)

print(n-1, flush=True)
s = _input()
right = (n-1, s)

print(n//2, flush=True)
s = _input()
center = (n//2, s)

while(True):
    if check(left, center):
        left = center
        new_i = (center[0] + right[0]) // 2
        print(new_i, flush=True)
        center = (new_i, _input())
    else:
        right = center
        new_i = (left[0] + center[0]) // 2
        print(new_i, flush=True)
        center = (new_i, _input())

Solution (Python):

import sys

def query(i, memo={}):
    if i in memo:
        return memo[i]
    print(i)
    sys.stdout.flush()
    s = input()
    if s == 'Male':
        memo[i] = 0
    elif s == 'Female':
        memo[i] = 1
    else:
        sys.exit()
    return memo[i]

n = int(input())
l, r = -1, n
while True:
    m = (l + r) // 2
    if query(0) ^ query(m) == m & 1:
        l = m
    else:
        r = m

Solution (Python):
N = int(input())
print(N-1, flush=True)
x = input()
if x == 'Vacant':
    exit(0)
print(0, flush=True)
s = input()
if s == 'Vacant':
    exit(0)
left = 0
right = N-1
mid = (right+left)//2
while True:
    print(mid, flush=True)
    t = input()
    if t == 'Vacant':
        exit(0)
    if bool(s == t) ^ bool((mid-left) % 2 == 0):
        right = mid
    else:
        left = mid
        s = t
    mid = (left+right)//2

Solution (Python):
N = int(input())
 
def query(x):
    print(x, flush=True)
    response = input()
    if response == "Vacant":
        exit()
    return response
 
lb = 0
ub = N - 1

l_query = query(lb)
u_query = query(ub)

while True:
    m = (lb + ub) // 2
    m_query = query(m)
    if (m_query == l_query) == (m % 2 == lb % 2):
        lb = m
        l_query = m_query
    else:
        ub = m

Solution (Python):
N = int(input())
low = 0
high = N - 1
t = (low + high) // 2
flag = 0
print(0)
resl = input()
print(N-1)
resr = input()
if resl == "Vacant" or resr == "Vacant":
    flag = 1

while(flag == 0):
    print(t)
    inp = input()
    if inp == "Vacant":
        break
    if (high-t) % 2 == 0 and inp != resr:
        low = t
        resl = inp
    elif (high-t) % 2 == 1 and inp == resr:
        low = t
        resl = inp
    elif (t-low) % 2 == 0 and inp != resl:
        high = t
        resr = inp
    else:
        high = t
        resr = inp
    t = (low + high) // 2

Solution (Python):
import sys 

def func():
    n=int(input())
    print(0)
    sys.stdout.flush()
    gl=input()
    if gl == 'Vacant': 
        return
    print(n-1)
    sys.stdout.flush()
    gr=input()
    if gr == 'Vacant':
        return
    l=0
    r=n-1
    m=0
    while l<r-1:
        m=(l+r)>>1
        print(m)
        sys.stdout.flush()
        gm=input()
        if gm == 'Vacant' : 
            return  
        if (m-l)%2==0 and gm==gl :
            l=m
        elif (m-l)%2==1 and gm!=gl : 
            gl=gm
            l=m
        else :
            gr=gm
            r=m

    if m==l : 
        print(r)
        sys.stdout.flush()
    else: 
        print(l)
        sys.stdout.flush()
    return 

func()

Solution (Python):
import sys
 
N = int(input())
 
A =[ [0 for i in range(2)]for i in range(20)]
 
if N < 20:
    for i in range(N):

        print(i)
        print("", flush=True)
    
    S = input()
    if S == 'Vacant':
        sys.exit()
 
else:
    nS = 0
    nE = N - 1
    
    nQ = 0 
    print(nQ)
    print("", flush=True) 
    S = input()
    if S == 'Vacant':
        sys.exit()
 
 
    nQ = N - 1
    print(nQ)
    print("", flush=True)
    E = input()
    if E == 'Vacant':
        sys.exit()
 
    for i in range(20):
        nQ = ( nS + nE ) // 2
        print(nQ)
        print("", flush=True)
    
        S1 = input()
        if S1 == 'Vacant':
            sys.exit()
 
        nT2 = (nQ - nS) % 2
 
        if ( nT2 != 0 ) and ( S ==S1 ):
            E = S1
            nE = nQ
        elif ( nT2 == 0 ) and ( S !=S1 ):
            E = S1
            nE = nQ
        elif ( nT2 != 0 ) and ( S !=S1 ):
            S = S1
            nS = nQ
        elif ( nT2 == 0 ) and ( S ==S1 ):
            S = S1
            nS = nQ

Solution (Python):
n = int(input())
l = 0
r = n-1
mid = (l+r)/2
print(l)
s1 = raw_input()
if s1 == 'Vacant':
    exit(0)
print(mid)
s2 = raw_input()
if s2 == 'Vacant':
    exit(0)
while True:
    
    if (mid-l) % 2 == int(s1 != s2):
        l = mid
        s1 = s2
    else:
        r = mid
    
    mid = (l+r)/2
    if mid == l:
        break
    print(mid)
    s2 = raw_input()
    if s2 == 'Vacant':
        exit(0)
print(mid+1)
s1 = raw_input()

Solution (Python):
import sys


def ask(n):
    print n
    sys.stdout.flush()
    ans = raw_input()
    if ans == 'Female':
        return 0
    elif ans == 'Male':
        return 1
    else:
        exit()


N = input()
x = ask(0)
l = 1
r = N-1
lx = x
rx = x

while True:
    m = (l + r) / 2
    x = ask(m)
    if (m - l + 1) % 2 == 0 and lx != x:
        r = m - 1
        rx = x
    elif (m - l + 1) % 2 == 1 and lx == x:
        r = m - 1
        rx = x
    elif (r - m + 1) % 2 == 0 and rx != x:
        l = m + 1
        lx = x
    elif (r - m + 1) % 2 == 1 and rx == x:
        l = m + 1
        lx = x
    else:
        r = m - 1
        rx = x

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

def check(l, r, a, b):
	if (a != b):
		return ((r - l + 1) % 2 == 1)
	else:
		return ((r - l + 1) % 2 == 0)

def get(k):
	print(k - 1)
	return d[input()]

def main():
	n = int(input())
	left = get(1)
	if (left == 0): return
	right = get(n)
	if (right == 0): return

	l, r = 1, n
	while (l + 2 < r):
		m = (l + r) // 2
		med = get(m)
		if (med == 0): return
		if (check(l, m, left, med)):
			right, r = med, m
		else:
			left, l = med, m
	get(l + 1)

main()

Solution (Python):

N = int(input())

def query(x):
    print(x, flush=True)
    res = input()
    if res == 'Vacant':
        exit()
    return res

l, r = 0, N - 1
ql = query(l)
qr = query(r)
while True:
    m = (l + r) // 2
    qm = query(m)
    if (qm == ql) == (m % 2 == l % 2):
        l = m
        ql = qm
    else:
        r = m

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

rl = [0, N-1]
rl_condition = ["",""]
flag = True

for i, RL in enumerate(rl):
   print(RL)
   print("\n")
   s = input()
   rl_condition[i] = s
   if s == "Vacant":
      flag = False
      break

while flag:
   center = (rl[0] + rl[1])//2
   print(center)
   print("\n")
   s = input()
   if s == "Vacant":
      break
   elif ((center - rl[0])%2 == 1) and (s == rl_condition[0]):
      rl_condition[1] = s
      rl[1] = center
      continue
   elif ((rl[1] - center)%2 == 1) and (s == rl_condition[1]):
      rl_condition[0] = s
      rl[0] = center
      continue
   elif ((center - rl[0])%2 == 0) and (s != rl_condition[0]):
      rl_condition[1] = s
      rl[1] = center
      continue
   elif ((rl[1] - center)%2 == 0) and (s != rl_condition[1]):
      rl_condition[0] = s
      rl[0] = center
      continue

Solution (Python):
import sys

N=int(input())
st=0
en=N
print(st)
sys.stdout.flush()
s=input().split()
if s=="Vacant":
  sys.exit()
a=st
b=en
c=s
d=s

for i in range(19):
  x=(a+b)//2
  print(x)
  sys.stdout.flush()
  f=input().split()

  if f=="Vacant":
    sys.exit()
  elif (x-a)%2==0 and c!=f:
    b=x
    d=f
  elif (x-a)%2==0 and c==f:
    a=x
    c=f
  elif (x-a)%2==1 and c!=f:
    a=x
    c=f
  elif (x-a)%2==1 and c==f:
    b=x
    d=f

Solution (Python):
n = int(input())
print(0)
L = R = input()
if L == "Vacant":
    exit()

l = 0
r = n
while True:
    m = (l + r) // 2
    print(m)
    M = input()
    if M == "Vacant":
        exit()
    if (M == L) ^ ((m - l) % 2 == 1):
        l = m
        L = M
    else:
        r = m
        R = M

Solution (Python):
N = int(input())
seats = [""] * N


print(0)
seats[0] = input()
if seats[0] == "Vacant":
    exit()
print(N - 1)
seats[N - 1] = input()
if seats[N - 1] == "Vacant":
    exit()

l = 0
r = N - 1
while True:
    m = (l + r) // 2
    print(m)

    s = input()
    if s == "Vacant":
        exit()
    seats[m] = s

    if (seats[l] == seats[m]) & ((m - l) % 2 == 1):
        r = m
    elif (seats[l] != seats[m]) & ((m-l) % 2 == 0):
        r = m
    else:
        l = m

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


def is_male(res):
    return True if res == 'Male' else False

l = 0
h = N
print(l)
prev_sex = is_male(input())
while True:
    print((h + l) // 2)
    res = input()
    if res == 'Vacant':
        break
    sex = is_male(res)
    if (((h + l) // 2 - l) % 2 == 0 and sex != prev_sex) or (((h + l) // 2 - l) % 2 == 1 and sex == prev_sex):
        h = (h + l) // 2
    else:
        l = (h + l) // 2
        prev_sex = sex

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


def query(num):
    print(num)
    return input()


result = [-1] * (N + 1)
result[0] = query(0)
result[N] = result[0]
edge = [0, N]
if result[0] == "Vacant":
    sys.stdout.flush()
else:
    for i in range(30):
        idx = int(abs(edge[0] - edge[1]) / 2) + min(edge)
        result[idx] = query(idx)
        if result[idx] == "Vacant":
            sys.stdout.flush()
            break
        for i in range(2):
            r = result[edge[i]]
            if abs(edge[i] - idx) % 2 == 0:
                if r != result[idx]:
                    if i == 0:
                        edge[1] = idx
                        break
                    else:
                        edge[0] = idx
                        break
            elif abs(edge[i] - idx) % 2 == 1:
                if r == result[idx]:
                    if i == 0:
                        edge[1] = idx
                        break
                    else:
                        edge[0] = idx
                        break
    sys.stdout.flush()

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

print(0)
MorF = input()
if MorF == 'Vacant':
    exit()

iSt = 1
iEn = N - 1
seat = MorF
while True:
    iMid = (iSt + iEn) // 2

    print(iMid)
    MorF = input()
    if MorF == 'Vacant':
        break

    if MorF == seat:
        if (iMid - iSt) % 2:
            iSt = iMid + 1
            seat = MorF
        else:
            iEn = iMid - 1
    else:
        if (iMid - iSt) % 2:
            iEn = iMid - 1
        else:
            iSt = iMid + 1
            seat = MorF

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    pf(0)
    ta = ti = S()
    if ti == 'Vacant':
        return
    mi = 0
    ma = n
    while 1:
        mm = (mi+ma) // 2
        pf(mm)
        c = S()
        if c == 'Vacant':
            return
        if ti == c:
            if (mm - mi) % 2 == 0:
                mi = mm
                ti = c
            else:
                ma = mm
                ta = c
        else:
            if (mm - mi) % 2 == 1:
                mi = mm
                ti = c
            else:
                ma = mm
                ta = c

    return 'No'


main()

Solution (Python):
def query(seat,m_max,m_min,seat_0):
    print(seat)
    s=input()

    if (seat%2==0 and s==seat_0) or (seat%2==1 and s!=seat_0):
        m_min=seat
        seat=int(0.5*(m_max+seat))
            
    else :
        m_max=seat
        seat=int(0.5*(m_min+seat))

    query(seat,m_max,m_min,seat_0)

n=int(input())
print(0)
query(int(0.5*n), n, 0, input())

Solution (Python):
def male_or_female(seat,m_max,m_min,seat_0):
    print(seat)
    s=input()

    if (seat%2==0 and s==seat_0) or (seat%2==1 and s!=seat_0):
        m_min=seat
        seat=int(0.5*(m_max+seat))
            
    else :
        m_max=seat
        seat=int(0.5*(m_min+seat))

    male_or_female(seat,m_max,m_min,seat_0)

n=int(input())
print(0)
male_or_female(int(0.5*n), n, 0, input())

Solution (Python):
def male_or_female(seat,m_max,m_min,seat_0):
    global seat_check, n_max, n_min
    print(seat)
    s=input()

    if (seat%2==0 and s==seat_0) or (seat%2==1 and s!=seat_0):
        n_min=seat
        seat=int(0.5*(m_max+seat))
        seat_check=seat
            
    else :
        n_max=seat
        seat=int(0.5*(m_min+seat))
        seat_check=seat
            
n_max=int(input())
n_min=0

print(0)
seat_zero=input()
seat_check=int(0.5*n_max)

for i in range(19):
    male_or_female(seat_check, n_max, n_min, seat_zero)