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




from collections import defaultdict, Counter, deque








def main():
    n = int(input())
    print(0)
    v = input()
    if v == "Vacant":
        exit()
    l, r = 0, n - 1
    while True:
        m = (l+r)//2
        print(m)
        q = input()
        if q == "Vacant":
            exit()
        elif m % 2 != 0:
            if v == q:
                r = m 
            else:
                l = m + 1
        else:
            if v == q:
                l = m+1
            else:
                r = m 


if __name__ == '__main__':
    main()

Solution (Python):
import sys


def solve(mid):
    print(mid)
    sys.stdout.flush()
    mid_state = input()
    if mid_state == "Vacant":
        print(mid)
        exit()
    if ok % 2 == mid % 2:
        if ok_state == mid_state:
            return True, mid_state
        else:
            return False, mid_state
    else:
        if ok_state == mid_state:
            return False, mid_state
        else:
            return True, mid_state

n = int(input())

print(0)
sys.stdout.flush()
ok = 0
ok_state = input()
if ok_state == "Vacant":
    print(0)
    exit()
    
print(n-1)
sys.stdout.flush()
ng = n-1
ng_state = input()
if ng_state == "Vacant":
    print(n-1)
    exit()


while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    judge, state = solve(mid)
    if judge:
        ok = mid
        ok_state = state
    else:
        ng = mid
        ng_state = state
print(ok)
exit()

Solution (Python):
import sys

n = int(input())
l = 0
r = n-1
mid = r // 2
re = [None] * n
print(0, flush=True)
re[0] = input()
if re[0] == "Vacant":
  sys.exit()
print(n-1, flush=True)
re[n-1] = input()
if re[n-1] == "Vacant":
  sys.exit()
print(mid, flush=True)
re[mid] = input()
while re[mid] != "Vacant":
  if re[l] == re[mid]:
    if (mid - l) % 2:
      r = mid
    else:
      l = mid
  else:
    if (mid - l) % 2:
      l = mid
    else:
      r = mid
  mid = (l + r) // 2
  print(mid, flush=True)
  re[mid] = input()
else:
  sys.exit()

Solution (Python):

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

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

def solve():
    n = I()
    print(0)
    flush
    s = input()
    l = 0
    r = n
    s0 = s
    while s != "Vacant":
        m = (l+r) >> 1
        print(m)
        flush
        s = input()
        if m&1:
            if s == s0:
                r = m
            else:
                l = m
        else:
            if s != s0:
                r = m
            else:
                l = m
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
n=int(input())
b=True
print(0)
w1=input()
if w1=="Vacant":
  b=False
  sys.exit()
print(n-1)
w2=input()
if w2=="Vacant":
  b=False
  sys.exit()
left=0
right=n-1
count=2
while b and count<20:
  mid=(left+right)//2
  print(mid)
  w=input()
  count+=1
  if w=="Vacant":
    b=False
    sys.exit()
  else:
    if left%2==mid%2 and w1!=w:
      right=mid
      w2=w
    elif left%2!=mid%2 and w1==w:
      right=mid
      w2=w
    elif right%2==mid%2 and w2!=w:
      left=mid
      w1=w
    elif right%2!=mid%2 and w2==w:
      left=mid
      w1=w

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

l=0
print(l)
sys.stdout.flush()
sl=input()
if sl=="Vacant":
    exit()
r=n-1
print(r)
sys.stdout.flush()
sr=input()
if sr=="Vacant":
    exit()



for _ in range(18):
    m=(l+r)//2
    print(m)
    sys.stdout.flush()
    s=input()
    if s=="Vacant":
        exit()
    if (m-1-l)%2 and s!=sl:
        sr=s
        r=m
    if (m-1-l)%2==0 and s==sl:
        sr=s
        r=m
    if (r-m-1)%2 and s!=sr:
        sl=s
        l=m
    if (r-m-1)%2==0 and s==sr:
        sl=s
        l=m

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

def solve() :
    print(0)
    zero = input()
    
    if zero == 'Vacant' :
        return
        
    ok, ng = 0, N
    while ng - ok > 1 :
        mid = (ok + ng) // 2
        
        print(mid)
        rep = input()
        if rep == 'Vacant' :
            return
            
        if (mid % 2 == 0 and rep != zero) or (mid % 2 == 1 and rep == zero) :
            ng = mid
        else :
            ok = mid
        
solve()

Solution (Python):

from collections import defaultdict


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


def main():
	N = int(input())
	print(0, flush=True)
	s = input()
	if s != "Vacant":
		left = 0
		leftM = s
		print(N - 1, flush=True)
		s = input()
		if s != "Vacant":
			right = N - 1
			rightM = s
			while True:
				mid = (left + right) // 2
				print(mid, flush=True)
				s = input()
				if s == "Vacant":
					break
				elif (mid - left) % 2 == 0 and s != leftM or (mid - left) % 2 != 0 and s == leftM:
					right = mid
					rightM = s
				else:
					left = mid
					leftM = s

if __name__ == '__main__':
	main()

Solution (Python):
n=int(input())
print(0)
z=input()[0]
if z=="V":
    exit()
def f(i):
    print(i)
    s=input()[0]
    if s=="V":
        exit()
    if i%2==0:
        if s==z:
            return False
        else:
            return True
    else:
        if s==z:
            return True
        else:
            return False
f(n-1)
left=0
right=n-1
while right-left>1:
    mid=(left+right)//2
    if f(mid):
        right=mid   
    else:
        left=mid
exit()

Solution (Python):
import sys

N = int(input())

print (0)
l = 0
ln = input()

if ln == "Vacant":
    sys.exit()

print (N-1)
r = N-1
rn = input()

if rn == "Vacant":
    sys.exit()


while True:

    mid = (l + r) // 2
    print (mid)
    mn = input()

    if mn == "Vacant":
        sys.exit()

    if (mid - l) % 2 == 0:

        if ln == mn:
            l = mid
            ln = mn

        else:
            r = mid
            rn = mn

    else:

        if ln == mn:
            r = mid
            rn = mn

        else:
            l = mid
            ln = mn

Solution (Python):
N = int(input())
l = 0
r = (N - 1)
m = (l + r) // 2

print(l)
l_stat = input()
if l_stat == "Vacant":
  exit()

print(m)
m_stat = input()
if m_stat == "Vacant":
  exit()

while True:
  if ((m - l) % 2 == 0 and l_stat == m_stat) or ((m - l) % 2 == 1 and l_stat != m_stat):
    l, m = m, (m + r + 1) // 2
    l_stat = m_stat
    print(m)
    m_stat = input() 
    if m_stat == "Vacant":
      exit()
  else:
    m, r = (l + m) // 2, m
    print(m)
    m_stat = input()
    if m_stat == "Vacant":
      exit()

Solution (Python):
n=int(input())
l,r=0,n
print(0,flush=True)
s=input()
sl,sr=s,s
while True:
  m=(l+r)//2
  print(m,flush=True)
  sm=input()
  if (sm==sl)+((m-l)%2)==1:
    l=m
    sl=sm
  else:
    r=m
    sr=sm

Solution (Python):
n=int(input())
l,r=0,n
print(0,flush=True)
s=input()
sl,sr=s,s
while True:
  m=(l+r)//2
  print(m,flush=True)
  sm=input()
  if sm==sl and (m-l)%2==0:
    l=m
    sl=sm
  elif sm!=sl and (m-l)%2!=0:
    l=m
    sl=sm
  else:
    r=m
    sr=sm

Solution (Python):
n=int(input())
l,r=0,n
print(0,flush=True)
s=input()
sl,sr=s,s
if s!="Vacant":
  while True:
    m=(l+r)//2
    print(m,flush=True)
    sm=input()
    if sm==sl and (m-l)%2==0:
      l=m
      sl=sm
    elif sm!=sl and (m-l)%2!=0:
      l=m
      sl=sm
    else:
      r=m
      sr=sm

Solution (Python):
def main():
    n = int(input())
    i = 0
    d = {"Vacant": 2, "Male": 0, "Female": 1}
    print(i)
    s = d[input()]
    if s == 2:
        return 0
    lower = 0
    upper = n - 1
    while True:
        mid=lower+(upper-lower)//2
        print(mid)
        s2 = d[input()]
        if s2 == 2:
            return 0
        if mid > i:
            if abs(mid - i) % 2 == (s != s2):
                lower = mid+1
            else:
                upper = mid
        else:
            if abs(mid - i) % 2 == (s != s2):
                upper = mid
            else:
                lower = mid+1
        i = mid
        s=s2
main()

Solution (Python):


N=int(input())

l=0
r=N

print(l,flush=True)
bstate=input()

if bstate!="Vacant":
    while True:
        
        L=int((r-l)/2)
        if (L%2)==0:
            L-=1
        c=l+L
        c=max(l+1,c)
        c=min(r-1,c)
        
        print(c,flush=True)
        state=input()
        if state=="Vacant":
            break

        if state!=bstate:
            l=c
        else:
            r=c

        bstate=state

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


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


def test(l, r, l_resp, r_resp):
    if l % 2 == r % 2:
        return l_resp == r_resp
    else:
        return l_resp != r_resp


resp = ask(0)

l = 0
r = N
l_resp = resp
r_resp = resp

for _ in range(19):
    m = (l+r)//2
    m_resp = ask(m)
    if test(l, m, l_resp, m_resp):
        l, l_resp = m, m_resp
    else:
        r, r_resp = m, m_resp

Solution (Python):
from collections import namedtuple
from functools import partial
from operator import attrgetter

Path = namedtuple('Path', ('length', 'left_seat', 'right_seat'))

m = set()
f = set()


def is_suitable_path(p: 'Path', m: 'set', f: 'set') -> 'bool':
    if p.length <= 1:
        return False
    if p.length % 2 == 0:
        return (p.left_seat in m and p.right_seat in f) or (p.left_seat in f and p.right_seat in m)
    else:
        return (p.left_seat in m and p.right_seat in m) or (p.left_seat in f and p.right_seat in f)


is_suitable_path = partial(is_suitable_path, m=m, f=f)

n = int(input())

checked = [n]
x = 0
for _ in range(20):
    print(x, flush=True)

    checked.append(x)
    checked.sort()

    res = input()
    if res[0] == 'V':
        break
    else:
        if res[0] == 'M':
            m.add(x)
            if x == 0:
                m.add(n)
        else:
            f.add(x)
            if x == 0:
                f.add(n)

        t = sorted(filter(is_suitable_path,
                          (Path(length=t - s, left_seat=s, right_seat=t) for s, t in zip(checked, checked[1:]))),
                   key=attrgetter('length'))
        x = (t[0].left_seat + t[0].right_seat) // 2

Solution (Python):
from collections import namedtuple
from functools import partial
from operator import attrgetter

Path = namedtuple('Path', ('length', 'left_seat', 'right_seat'))

m = set()
f = set()


def is_suitable_path(p: 'Path', m: 'set', f: 'set') -> 'bool':
    if p.length <= 1:
        return False
    if p.length % 2 == 0:
        return (p.left_seat in m and p.right_seat in f) or (p.left_seat in f and p.right_seat in m)
    else:
        return (p.left_seat in m and p.right_seat in m) or (p.left_seat in f and p.right_seat in f)


is_suitable_path = partial(is_suitable_path, m=m, f=f)

n = int(input())

checked = [n]
x = 0
for _ in range(20):
    print(x)

    checked.append(x)
    checked.sort()

    res = input()
    if res[0] == 'V':
        break
    else:
        if res[0] == 'M':
            m.add(x)
            if x == 0:
                m.add(n)
        else:
            f.add(x)
            if x == 0:
                f.add(n)

        t = sorted(filter(is_suitable_path,
                          (Path(length=t - s, left_seat=s, right_seat=t) for s, t in zip(checked, checked[1:]))),
                   key=attrgetter('length'))
        x = (t[0].left_seat + t[0].right_seat) // 2

Solution (Python):
from collections import namedtuple
from functools import partial
from operator import attrgetter

Path = namedtuple('Path', ('length', 'left_seat', 'right_seat'))

m = set()
f = set()


def is_suitable_path(p: 'Path', m: 'set', f: 'set') -> 'bool':
    if p.length <= 1:
        return False
    if p.length % 2 == 0:
        return (p.left_seat in m and p.right_seat in f) or (p.left_seat in f and p.right_seat in m)
    else:
        return (p.left_seat in m and p.right_seat in m) or (p.left_seat in f and p.right_seat in f)


is_suitable_path = partial(is_suitable_path, m=m, f=f)

n = int(input())

checked = [n]
x = 0
for _ in range(20):
    print(x)

    checked.append(x)
    checked.sort()

    res = input()
    if res[0] == 'V':
        break
    else:
        if res[0] == 'M':
            m.add(x)
            if x == 0:
                m.add(n)
        else:
            f.add(x)
            if x == 0:
                f.add(n)

        t = sorted(filter(is_suitable_path,
                          (Path(length=t - s, left_seat=s, right_seat=t) for s, t in zip(checked, checked[1:]))),
                   key=attrgetter('length'))
        x = (t[0].left_seat + t[0].right_seat) // 2

Solution (Python):

n = int(input())
s = [0] * (n + 1)

print(0)
a = input()
if a == 'Vacant':
    exit()
s[0], s[n] = a, a
l, r = 0, n
while True:
    m = (r + l) // 2
    print(m)
    a = input()
    if a == 'Vacant':
        exit()
    s[m] = a
    if s[l] == s[m]:
        if (l - m) % 2 == 1:
            r = m
        else:
            l = m
    else:
        if (l - m) % 2 == 1:
            l = m
        else:
            r = m

Solution (Python):
n = int(input())
s = [0]*(n+1)

print(0)
a = input()
if a == "Vacant":
    exit()
s[0] = a
s[n] = a

l = 0
r = n
while True:
    m = (r+l)//2
    print(m)
    a = input()
    if a == "Vacant":
        exit()

    s[m] = a
    if s[l] == s[r]:
        if s[l] == s[m]:
            if (m-l) % 2 == 1:
                r = m
            else:
                l = m
        else:
            if (m-l) % 2 == 1:
                l = m
            else:
                r = m
    else:
        if s[l] == s[m]:
            if(m-l) % 2 == 1:
                r = m
            else:
                l = m
        else:
            if(m-l) % 2 == 1:
                l = m
            else:
                r = m

Solution (Python):
import sys
n=int(input())
print(0)
l=input()
L=0
if l=='Vacant':
  sys.exit()
print(n-1)
r=input()
R=n-1
if r=='Vacant':
  sys.exit()

while True:
  print((L+R)//2)
  x=input()
  X=(L+R)//2
  if x=='Vacant':
    sys.exit()
  if ((X-L)%2==1 and x==l) or ((X-L)%2==0 and x!=l):
    r=x;R=X
  else:
    l=x;L=X

Solution (Python):

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

    checked = [0]*(N+1)

    print(0)
    A = input()
    if A == 'Vacant':
        return
    elif A == 'Male':
        checked[0] = 1
        checked[N] = 1
    else:
        checked[0] = -1
        checked[N] = -1
    l = 0
    r = N
    m = (l+r)//2
    while l < r:
        print(m)
        A = input()
        if A == 'Vacant':
            return
        elif A == 'Male':
            checked[m] = 1
        else:
            checked[m] = -1

        if (m - l) % 2 == 1:
            if checked[l] != checked[m]:
                l = m
            else:
                r = m
        else:
            if checked[l] == checked[m]:
                l = m
            else:
                r = m
        m = (l+r)//2



if __name__ == "__main__":
    main()

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


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

if first == 'Vacant':
    exit()

if first == 'Male':
    first = 1
else:
    first = -1

notHas = 1
has = N - 1

while has - notHas > 1:
    mid = (notHas + has) // 2
    print(mid, flush=True)
    ret = input()

    if ret == 'Vacant':
        exit()

    if ret == 'Male':
        ret = 1
    else:
        ret = -1

    trueValue = first * (-1)**(mid % 2)
    if ret == trueValue:
        notHas = mid
    else:
        has = mid

print(notHas, flush=True)
ret = input()

if ret == 'Vacant':
    exit()

print(has, flush=True)
input()
exit()

Solution (Python):

def main():
    
    
    N = int(input())
    print(0, flush=1)
    seat_zero = input().rstrip()
    if seat_zero == "Vacant":
        return
    left, right = 0, N
    for _ in range(19):
        mid = (left + right) // 2
        print(mid, flush=1)
        this_seat = input().rstrip()
        if this_seat == "Vacant":
            return
        if mid % 2 == (seat_zero != this_seat):
            left = mid
        else:
            right = mid


if __name__ == "__main__":
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
flush = sys.stdout.flush
def query(x):
    print("%d\n" % x)
    flush()
    
    return readline().strip()


n = int(input())

right = n-1
left = 0

print(0, flush = True)
lefti = input()
if lefti == "Vacant":
    exit(0)
print(n-1, flush = True)
righti = input()
if righti == "Vacant":
    exit(0)

while True:
    mid = left + (right-left)//2
    midi = query(mid)
    if midi == "Vacant":
        exit(0)
    if (lefti == midi and (mid - left) % 2 == 1) or ((lefti != midi) and (mid - left) % 2 == 0):
        righti = midi
        right = mid
    else:
        lefti = midi
        left = mid

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

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

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

resp = ask(0)

L = 0
R = N
resp_L = resp_R = resp

for i 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
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline


N = int(input())





x = 0
y = N

p = [None] * N
print(x, flush = True)
p[x] = input().strip()

for _ in range(20):
    m = (x + y) // 2
    print(m, flush = True)

    s = input().strip()
    if s == "Vacant":
        exit()
    else:
        if p[x] == s:
            if (m - x) % 2 == 0:
                x = m
                p[x] = s
            else:
                y = m
                p[y] = s
        else:
            if (m - x) % 2 == 0:
                y = m
                p[y] = s
            else:
                x = m
                p[x] = s

Solution (Python):
n=int(input())
print(0, flush=True)
sl=input()
if sl=="Vacant":
  exit(0)

l=0
r=n-1

for i in range(30):

  if r-l<=2:
    for j in range(3):
      print(l+j+1, flush=True)
      s=input()
      if s=="Vacant":
        exit(0)

      
  elif ((l+r)//2)%2==0:
    print((l+r)//2, flush=True)
    s=input()
    if s=="Vacant":
      exit(0)
    elif s==sl:
      l=(l+r)//2
      sl=s
    else:
      r=(l+r)//2
      sr=s

  else:
    print((l+r)//2+1, flush=True)
    s=input()
    if s=="Vacant":
      exit(0)
    elif s==sl:
      l=(l+r)//2
      sl=s
    else:
      r=(l+r)//2
      sr=s

Solution (Python):
n=int(input())
s = [0] * (n+1)

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

l = 0
r = n
while True:
    m = (r+l)//2
    print(m)
    a = input()
    if a=='Vacant':
        exit()
    s[m]=a
    if s[l]==s[r]:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m
    else:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m

Solution (Python):
n=int(input())
s = [0] * (n+1)

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

l = 0
r = n
while True:
    m = (r+l)//2
    print(m)
    a = input()
    if a=='Vacant':
        exit()
    s[m]=a
    if s[l]==s[r]:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m
    else:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m

Solution (Python):
n=int(input())
s = [0] * (n+1)

print(0,flush=True)
a = input()
if a=='Vacant':
    exit()
s[0]=a
s[n]=a

l = 0
r = n
while True:
    m = (r+l)//2
    print(m,flush=True)
    a = input()
    if a=='Vacant':
        exit()
    s[m]=a
    if s[l]==s[r]:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m
    else:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def check(str0, left, right):

    if right - left <= 1:
        print(left)
        now_str = input()
        if now_str == 'Vacant':
            sys.exit()
        print(right)
        now_str = input()
        if now_str == 'Vacant':
            sys.exit()

    half = (left + right) // 2

    print(half)
    half_str = input()
    if half_str == 'Vacant':
        sys.exit()

    if (half_str == str0 and half % 2) or (half_str != str0 and half % 2 == 0):
        check(str0, left, half)
    else:
        check(str0, half, right)


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

    print(0)
    str0 = input()
    if str0 == 'Vacant':
        sys.exit()

    check(str0, 0, num)




if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
seat = ['?' for _ in range(N+1)]
left = 0
right = N
for i in range(20):
  if i == 0:
    output = 0
  else:
    output = (right + left)//2
  print(output)
    
  s = input()
  if s == 'Vacant':
    exit()
  seat[output] = s
  if i == 0:
    seat[N] = s
  
  if ((right + output) % 2 == 0 and seat[right] != seat[output]) or ((right + output) % 2 == 1 and seat[right] == seat[output]):
    left = output
  else:
    right = output

Solution (Python):
N = int(input())
seat = ['?' for _ in range(N+1)]
left = 0
right = N
for i in range(20):
  if i == 0:
    output = 0
  elif i == 1:
    output = (N-1)//2
  else:
    output = (right + left)//2
  print(output)
    
  s = input()
  if s == 'Vacant':
    exit()
  seat[output] = s
  if i == 0:
    seat[N] = s
  
  if ((right + output) % 2 == 0 and seat[right] != seat[output]) or ((right + output) % 2 == 1 and seat[right] == seat[output]):
    left = output
  else:
    right = output

Solution (Python):
n = int(input())
print(0)
left = input()[0]
if left == 'V':exit()
print(n-1)
right = input()[0]
if right == 'V':exit()

ok = 0
ng = n-1
while ng-ok > 1:
    mid = (ng+ok)//2
    print(mid)
    s = input()[0]
    if s == 'V':exit()
    if mid%2 == 0:
        if s == left:
            ok = mid
        else:
            ng = mid
    else:
        if s != left:
            ok = mid
        else:
            ng = mid

Solution (Python):
N=int(input())
print(0)
S0 = input()[0]
if S0=="V":exit()
print(N-1)
if input()[0]=="V":exit()

l,r=0,N-1
while r-l>1:
    med=(r+l)//2
    print(med)
    S1=input()[0]
    if S1=="V":
        exit()
    elif (med%2==0 and S1==S0) or (med%2==1 and S1!=S0):
        l=med
    else:
        r=med
print(r)

Solution (Python):

def ask(i):
    print(i)
    return input()

def solve(l, r):
    m = (l + r) // 2
    res = ask(m)
    if res == "Vacant":
        quit()
    if (m % 2 == 0 and a0 == res) or (m % 2 == 1 and a0 != res):
        solve(m + 1, r)
    else:
        solve(l, m)

N = int(input())
a0 = ask(0)
if a0 == "Vacant":
    quit()
solve(1, N)

Solution (Python):
n = int(input())
def com(call):
  print(call)
  res = input()
  if res == "Vacant":
    exit(0)
  return res

resp = [None]*n
resp[0] = com(0)
resp[n-1] = com(n-1)

l = 0
r = n-1
while r-l>1:
  mid = (r+l)//2
  resp[mid] = com(mid)
  if ((r-mid)%2)==(resp[r]==resp[mid]):
    l = mid
  else:
    r = mid
com(l)
com(r)

Solution (Python):
N=int(input())
l,r=0,N
print(0)
s=input()
ls=s
if s!='Vacant':
    for i in range(19):
        x=l+(r-l)//2
        print(x)
        s=input()
        if s=='Vacant':
            break
        elif (x-l)%2==0 and s==ls or (x-l)%2==1 and s!=ls:
            l=x
            ls=s
        else:
            r=x

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):
def main():
    N=int(input())
    ans = [None]*N
    
    print(0)
    s=input()
    if s=="Vacant":return
    ans[0] = s=="Male"
    l=1
    r=N-1
    while l+1<r:
        i = (l+r)//2
        print(i)
        s=input()
        if s=="Vacant":return
        ans[i] = s=="Male"
        if (ans[i]==ans[0]) ^ (i%2!=0):
            l = i
        else:
            r = i
    print(l)
    s=input()
    if s=="Vacant":return
    print(r)
    return

main()

Solution (Python):
import sys
flush = sys.stdout.flush

d = {"M":0, "F":1}
def check(i):
    print(i)
    flush()
    s = input()
    if s[0] == "V":
        exit()
    return d[s[0]]

n = int(input())
left = 0
right = n-1
ls = check(left)
rs = check(right)

while right-left > 1:
    mid = (right+left)//2
    c = check(mid)
    if (c+mid-left)%2 == ls:
        left = mid
        ls = c
    else:
        right = mid

Solution (Python):
n=int(input())
l=0
center=(n-1)//2
r=n-1
print(center,flush=True)
ct=input()
if ct=='Vacant':
  exit()
print(l,flush=True)
lt=input()
if lt=='Vacant':
  exit()
print(r,flush=True)
rt=input()
if rt=='Vacant':
  exit()
flag=False
if (center-l)%2==0:
  if lt!=ct:
    r=center
    rt=ct
    flag=True
else:
  if lt==ct:
    r=center
    rt=ct
    flag=True
if flag==False:
  if (r-center)%2==0:
    if rt!=ct:
      l=center
      lt=ct
  else:
    if rt==ct:
      l=center
      lt=ct
while 1:
  center=(l+r)//2
  print(center,flush=True)
  ct=input()
  if ct=='Vacant':
    exit()
  flag=False
  if (center-l)%2==0:
    if lt!=ct:
      r=center
      rt=ct
      flag=True
  else:
    if lt==ct:
      r=center
      rt=ct
      flag=True
  if flag==False:
    if (r-center)%2==0:
      if rt!=ct:
        l=center
        lt=ct
    else:
      if rt==ct:
        l=center
        lt=ct

Solution (Python):
def solve():
  n=int(input())
  l=0
  r=n-1
  print(l,flush=True)
  lt=input()
  if lt=='Vacant':
    return
  print(r,flush=True)
  rt=input()
  if rt=='Vacant':
    return
  while 1:
    center=(l+r)//2
    print(center,flush=True)
    ct=input()
    if ct=='Vacant':
      return
    if (center-l)%2==0:
      if lt!=ct:
        r=center
        rt=ct
      else:
        l=center
        lt=ct
    else:
      if lt==ct:
        r=center
        rt=ct
      else:
        l=center
        lt=ct
solve()

Solution (Python):
import sys
fl=sys.stdout.flush
res=['Vacant','Male','Female']

def main():
    n=int(input())
    r=['' for _ in range(n)]
    print(0)
    fl()
    r[0]=input()
    if r[0]==res[0]:
        return
    
    print(n-1) 
    r[n-1]=input()
    fl()
    if r[n-1]==res[0]:
        return
    ll,rr=0,n-1
    while rr-ll>1:
        mid=(rr+ll)//2
        print(mid)
        fl()
        r[mid]=input()
        if r[mid]==res[0]:
            return
        if (r[mid]==r[rr])^((rr-mid)%2==0):
            ll=mid
        else:
            rr=mid
    
main()

Solution (Python):
import sys
n = int(input())
print(0, flush=True)
f, m = "Female", "Male"
s = input()
if s == "Vacant":
    quit()
x = 0 if s == f else 1
high = n-1
low = 0
while high - low > 1:
    mid = (high + low) // 2
    print(mid, flush=True)
    s = input()
    if s == "Vacant":
        sys.exit()
    if mid % 2 == x:
        if s == f:
            low = mid
        else:
            high = mid
    else:
        if s == f:
            high = mid
        else:
            low = mid
print(high, flush=True)
sys.exit()

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

print(0)
init_state = input().rstrip()
if init_state == "Vacant":
    exit()
if init_state == "Male":
    states = ["Male", "Female"]
else:
    states = ["Female", "Male"]

l = 0; r = n
while r - l > 1:
    mid = (r + l) // 2
    print(mid)
    new_state = input().rstrip()
    if new_state == "Vacant":
        exit()
    if new_state == states[mid % 2]:
        l = mid
    else:
        r = mid
print(r, l)

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


def question(i):
    print(i)
    s = input()
    if s == 'Male':
        return 0
    elif s == 'Female':
        return 1
    exit()


a = question(0)
A = ([a, 1 - a] * N)[:N]
lb = -1
rb = N
while True:
    mid = (lb + rb) // 2
    if question(mid) == A[mid]:
        lb = mid
    else:
        rb = mid

Solution (Python):
import sys


def query(S):
    print(S)
    sys.stdout.flush()
    return input()


def main():
    N = int(input())
    base = query(0)
    if base == "Vacant":
        return
    lo = 1
    hi = N-1
    while lo < hi:
        mid = (lo+hi) // 2
        ans = query(mid)
        if ans == "Vacant":
            return
        if (mid % 2 == 0 and ans == base) or \
           (mid % 2 == 1 and ans != base):
            lo = mid + 1
        else:
            hi = mid
    query(lo)


if __name__ == "__main__":
    main()