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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
l = 0
r = N-1

print(l, flush=True)
tmp = input()
if tmp == "Vacant":
	exit()

print(r, flush=True)
tmp2 = input()
if tmp2 == "Vacant":
	exit()

while 2 < r-l:
	p = l + (r - l)//2//2*2
	print(p, flush=True)

	Output = input()
	if Output == "Vacant":
		exit()
	elif Output == tmp:
		l = p
	elif Output == tmp2:
		r = p

print(((r+l)//2), flush=True)
Output = input()
if Output == "Vacant":
	exit()

Solution (Python):
import sys
def valid():
    s = input()
    if s=='Vacant':
        sys.exit()
    return 1 if s=='Male' else 0

n = int(input())
print(0, flush=True)
s_l = valid()
lidx = 0
ridx = n

while True:
    midx = (lidx+ridx)//2
    print(midx, flush=True)
    s_m = valid()
    if ((midx-lidx)%2==1) ^ (s_l==s_m):
        lidx = midx
        s_l = s_m
    else:
        ridx = midx

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

print(0)
lowg = input()
print(n-1)
highg = input()

if lowg=="Vacant":
  quit()
if highg=="Vacant":
  quit()

low =0 
high=n-1
mid = (n-1)//2
for i in range(20):
  print(mid)
  temp=input()
  if temp=="Vacant":
    quit()
  if (mid-low)%2==0:
    if lowg==temp:
      lowg=temp
      low=mid
    else:
      high=mid
  else:
    if lowg==temp:
      high=mid
    else:
      lowg=temp
      low=mid
  
  mid=(high+low)//2

Solution (Python):
import sys

input = sys.stdin.readline


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

    
    l, r = 0, N - 1
    print(l, flush=True)
    sl = input().rstrip()
    print(r, flush=True)
    sr = input().rstrip()
    if sl == "Vacant" or sr == "Vacant":
        exit()

    for _ in range(18):
        mid = (l + r) // 2
        print(mid, flush=True)
        s = input().rstrip()
        if s == "Vacant":
            exit()
        if (mid - l) % 2 == 0:
            if sl == s:
                l = mid
                sl = s
            else:
                r = mid
                sr = s
        else:
            if sl == s:
                r = mid
                sr = s
            else:
                l = mid
                sl = s


if __name__ == "__main__":
    main()

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
ret = ''

print(n-1)
sys.stdout.flush()
ret = sr()
rmanflag = True
if ret == 'Female':
    rmanflag = False
elif ret == 'Vacant':
    sys.exit()

print(0)
sys.stdout.flush()
ret = sr()
lmanflag = True
if ret == 'Female':
    lmanflag = False
elif ret == 'Vacant':
    sys.exit()

l = 0
r = n-1

m = (r-l)//2

while r > l:
    print(m)
    sys.stdout.flush()
    ret = sr()
    mmanflag = True
    if ret == 'Female':
        mmanflag = False
    elif ret == 'Vacant':
        sys.exit()
    
    
    if (m-l)%2==0:
        if lmanflag == mmanflag:
            l = m
            m = l+(r-l)//2
            lmanflag = mmanflag
        else:
            r = m
            m = l+(r-l)//2
            rmanflag = mmanflag
    else:
        if lmanflag == mmanflag:
            r = m
            m = l+(r-l)//2
            rmanflag = mmanflag
        else:
            l = m
            m = l+(r-l)//2
            lmanflag = mmanflag

Solution (Python):
def val():
    s = input()
    if s == "Vacant":
        exit()
    return 1 if s == "Male" else 0

N = int(input())

print(0, flush=True)

ofs = val()
l = 0
r = N

while True:
    m = (l+r)//2
    print(m, flush=True)
    s = val()^m & 1

    if ofs == s:
        l = m
    else:
        r = m

Solution (Python):
def val():
    s = input()
    if s == "Vacant":
        exit()
    return 1 if s == "Male" else 0


N = int(input())

print(0, flush=True)
ofs = val()
l = 0
r = N
while True:
    m = (l+r)//2
    print(m, flush=True)
    s = val() ^ m & 1

    if ofs == s:
        l = m
    else:
        r = m

    p = s

Solution (Python):
n = int(input())
left = 0
right = n
print(left)
sl = input()
if sl[0] == "V":
    quit()
while True:
    mid = (left + right) // 2
    print(mid)
    sm = input()
    if sm[0] == "V":
        quit()
    if ((mid - left) % 2 == 1) ^ (sl == sm):
        left = mid
        sl = sm
    else:
        right = mid

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

left = 0
right = n
print(left, flush=True)
sl = input()
if sl[0] == "V":
    quit()
while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    sm = input()
    if sm[0] == "V":
        quit()

    if ((mid - left) % 2 == 1) ^ (sl == sm):
        left = mid
        sl = sm
    else:
        right = mid

Solution (Python):
import sys
n = int(input())
D = {}
for i in [0,n-1]:
    print(i,flush=True)
    s = input()
    if s == "Vacant":
        sys.exit()
    D[i] = s
inf = 0
sup = n
while True:
    mid = (sup+inf)//2
    print(mid,flush=True)
    s = input()
    if s == "Vacant":
        sys.exit()
    else:
        D[mid] = s
        if ((mid%2==inf%2) != (D[mid] == D[inf])):
            sup = mid
        else:
            inf = mid

Solution (Python):


import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def query(q):
    print(q, flush=True)
    s = readline().decode().rstrip()
    if s[0] == 'V':
        sys.exit()
    return s


N = int(readline())

s = query(0)
l = 0
r = N
sex = s

while True:
    m = (l + r) // 2
    s = query(m)
    if sex == s:
        if (m - l) % 2:
            r = m
        else:
            l = m
    else:
        if (m - l) % 2:
            l = m
            sex = s
        else:
            r = m

Solution (Python):
import sys
n = int(input())
l = 0
r = n-1
print(0)
sys.stdout.flush()
i = input()
if i == "Vancant": exit()

for _ in range(19):
    m = (l+r)//2
    print(m)
    sys.stdout.flush()
    j = input()
    if j == "Vancant": exit()
    if (m-l)%2 == 0 and i != j: r = m-1
    elif (m-l)%2 == 1 and i == j: r = m-1
    else:
        l = m+1
        i = "Male" if j == "Female" else "Female"

Solution (Python):
import sys
n = int(input())
l = 0
r = n-1
print(0)
sys.stdout.flush()
i = input()
if i == "Vancant": exit()

for _ in range(19):
    m = (l+r)//2
    print(m)
    sys.stdout.flush()
    j = input()
    if j == "Vancant": exit()
    if (m-l)%2 == 0 and i != j: r = m-1
    elif (m-l)%2 == 1 and i == j: r = m-1
    else:
        l = m+1
        i = "Male" if j == "Female" else "Female"

Solution (Python):
def mfvinput(i):
    print(i)
    seat[i] = input()
    if seat[i] == 'Vacant':
        exit()

n = int(input())
seat = [None] * n

mfvinput(0), mfvinput(n - 1)
l, r = 0, n
for _ in range(20):
    tmp = (l + r) // 2
    mfvinput(tmp)
    if (tmp % 2 == l % 2) == (seat[tmp] == seat[l]):
        l = tmp
    else:
        r = tmp

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

print(0)
begin = input()

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

print(l)

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

print(0, flush=True)
s = input()
if s == 'Vacant':
    exit()
head_v = s
head_i = 0
print(n-1, flush=True)
s = input()
if s == 'Vacant':
    exit()
tail_v = s
tail_i = n-1

while True:
    mi = (head_i + tail_i) // 2
    print(mi, flush=True)
    mv = input()

    if mv == 'Vacant':
        exit()
    if tail_v == mv and (tail_i - mi) % 2 == 1 or tail_v != mv and (tail_i - mi) % 2 == 0:
        head_i = mi
        head_v = mv
    else:
        tail_i = mi
        tail_v = mv

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


def isOK(mid, x):
    print(str(mid), flush=True)
    s = input().strip()
    if s == "Vacant":
        exit()
    if (x and s == "Male") or (not x and s == "Female"):
        return True
    else:
        return False


ok = 0
ng = N

print("0", flush=True)
S = input().strip()
if S == "Vacant":
    exit()

if S == "Male":
    kijun = True
else:
    kijun = False

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if mid % 2 == 0:
        if isOK(mid, kijun):
            ok = mid
        else:
            ng = mid
    else:
        if isOK(mid, not kijun):
            ok = mid
        else:
            ng = mid

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

def query(i):
    print(i)
    s = input()[0]
    if s=='V':
        exit()
    return s

a = query(0)

def is_ok(k):
    if k==N: return False
    r = query(k)
    if k%2:
        return r != a
    else:
        return r == a

ok = 0
ng = N
while ng-ok > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m

Solution (Python):
import sys
import random

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def query(i):
    print(i)
    sys.stdout.flush()
    s = in_s()

    if s == 'Vacant':
        exit(0)
    elif s == 'Male':
        return 0
    elif s == 'Female':
        return 1


def main():

    N = in_n()

    min_i = 0
    max_i = N

    min_fm = query(0)
    max_fm = min_fm

    while max_i - min_i != 1:
        now_i = (min_i + max_i) // 2
        now_fm = query(now_i)

        if abs(now_i - min_i) % 2 == 0 and now_fm != min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - min_i) % 2 == 1 and now_fm == min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - max_i) % 2 == 0 and now_fm != max_fm:
            min_i = now_i
            min_fm = now_fm
        elif abs(now_i - max_i) % 2 == 1 and now_fm == max_fm:
            min_i = now_i
            min_fm = now_fm


if __name__ == '__main__':
    main()

Solution (Python):

N = int(input())
V, M, F = "Vacant", "Male", "Female"
left = 0
right = N
print(0)
s_left = input()
if s_left == V:
    exit()
while True:
    mid = (right + left) // 2
    print(mid)
    s_mid = input()
    if s_mid == V:
        exit()
    if s_left == s_mid:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            s_left = s_mid
        else:
            right = mid

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  l=0
  r=n-1

  print(0)
  _ans=S()
  if _ans=='Vacant':
    return
  l_ans=_ans

  print(n-1)
  _ans=S()
  if _ans=='Vacant':
    return
  r_ans=_ans

  while True:
    x=(l+r)//2
    print(x)

    ans=S()
    if ans=='Vacant':
      return

    if (x-l)%2==0:
      if l_ans==ans:
        l=x
      else:
        r=x
    else:
      if l_ans!=ans:
        l=x
        l_ans=ans
      else:
        r=x
        r_ans=ans

main()

Solution (Python):



import sys

def main():
    N = int(input())
    L = 0
    print(L)
    sys.stdout.flush()
    Ls = input()
    if Ls == "Vacant":
        exit()
    U = N-1
    print(U)
    sys.stdout.flush()
    Us = input()
    if Us == "Vacant":
        exit()
    for _ in range(18):
        mid = (U+L)//2
        if mid%2==1:
            mid-=1
        if mid==L:
            mid+=1
        print(mid)
        sys.stdout.flush()
        ms = input()
        if ms == "Vacant":
            exit()
        if Ls==ms:
            L=mid
        if Us==ms:
            U=mid

if __name__ == '__main__':
    main()

Solution (Python):
import sys
n = int(input())
le = 0
ri = n
print(0)
sys.stdout.flush()
s = input()
if s == "Male":
    ls = "Male"
elif s == "Female":
    ls = "Female"
else:
    exit()

while ri > le + 1:
    m = (ri+le)//2
    print(m)
    sys.stdout.flush()
    s = input()
    if s == "Vacant":
        exit()
    if (m-le)%2:
        if s == ls:
            ri = m
        else:
            le = m
            ls = s
    else:
        if s == ls:
            le = m
            ls = s
        else:
            ri = m
print(le)
sys.stdout.flush()
exit()

Solution (Python):
import sys
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
import sys
vals = [None]*n
def quest(q):
    print(q)
    sys.stdout.flush()
    res = input()
    if res=="Vacant":
        exit()
        res = -1
    elif res=="Male":
        res = 1
    else:
        res = 0
    vals[q] = res
    return res

k = n//2
res1 = quest(0)
res2 = quest(k)

if (res2-res1)%2 != k%2:
    l = 0
    r = k
else:
    l = k
    r = n
    
while l<r+1:
    m = (l+r)//2
    res = quest(m)
    if (res-vals[l])%2 != (l-m)%2:
        r = m
    else:
        l = m
quest(l)
quest(r)

Solution (Python):
N = int(input())
print(0,flush=True)
s = input().strip()
if s[0]!="V":
    x = s[0]
    low = 0
    high = N
    while high-low>1:
        mid = (high+low)//2
        print(mid,flush=True)
        s = input().strip()
        if s[0]=="V":
            break
        elif mid%2==0 and s[0]==x:
            low = mid
        elif mid%2==0 and s[0]!=x:
            high = mid
        elif mid%2==1 and s[0]==x:
            high = mid
        elif mid%2==1 and s[0]!=x:
            low = mid

Solution (Python):
import sys
n=int(input())
a=[-1]*n
print(0)
sys.stdout.flush()
a[0]=input()
l=0
print(n-1)
sys.stdout.flush()
r=n-1
a[n-1]=input()
while l!=r:
  if r==l+1:
    try1=r
  else:
    try1=(l+r)//2
  print(try1)
  sys.stdout.flush()
  a[try1]=input()
  if a[try1]=='Vacant':
    sys.exit()
  if ((r-try1)%2==0 and a[try1]!=a[r]) or ((r-try1)%2==1 and a[try1]==a[r]):
    l=try1
  else:
    r=try1

Solution (Python):
def is_ok(gen, res):
    if res == "Vacant":
        exit()
    return gen == res


def meguru_bisect_kai(ng, ok, gen):
    while True:
        mid = (ng + ok) // 2
        print(mid, flush=True)
        res = input()

        if is_ok(gen, res):
            if (mid - ng) % 2:
                ok = mid
            else:
                ng = mid
        else:
            if (mid - ng) % 2:
                ng = mid
                gen = res
            else:
                ok = mid


n = int(input())

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

ng = 0
ok = n
gen = res

meguru_bisect_kai(ng, ok, gen)

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

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

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Solution (Python):
n = int(input())
dat = [None] * n

def su(x):
    print(x)
    r = input()
    if r == "Vacant":
        return True
    elif r == "Male":
        dat[x] = "M"
        return False
    elif r == "Female":
        dat[x] = "F"
        return False
def do():
    if su(0):
        return 0
    if su(n-1):
        return 0
    l = 0
    r = n-1
    while True:
        mid = (l+r) // 2
        if su(mid):
            return 0

        if (mid - l) % 2 == 1: 
            if dat[l] == dat[mid]: 
                r = mid
                continue
        else: 
            if dat[l] != dat[mid]: 
                r = mid
                continue

        if (r - mid) % 2 == 1: 
            if dat[r] == dat[mid]: 
                l = mid
                continue
        else: 
            if dat[r] != dat[mid]: 
                l = mid
                continue
do()

Solution (Python):
import sys

N = int(input())

print(0)
ans_f = input()

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

l = 0
r = N-1
ans = ''
while r - l > 1:
    c = (l+r)//2
    print(c)
    ans = input()
    if ans == 'Vacant':
        sys.exit()
    if (ans == ans_f and c % 2 == 0) or (ans != ans_f and c % 2 == 1):
        l = c
    else:
        r = c

print(r)
ans = input()
if ans == 'Vacant':
    sys.exit()

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

l = 0
j = 0
r = N -1

print(0, flush=True)
a = input()
if a == 'Vacant':
  exit()
b = a
while r - l > 1:
  i = (r + l)//2
  print(i, flush=True)
  a = input()
  if a == 'Vacant':
    exit()
  if abs(i-j)%2 == 0:
    if a == b:
      if i > j:
        l = i
      else:
        r = i
    else:
      if i > j:
        r = i
      else:
        l = i
  else:
    if a == b:
      if i > j:
        r = i
      else:
        l = i
    else:
      if i > j:
        l = i
      else:
        r = i
      
  b = a
  j = i

print(l, flush=True)
a = input()
if a == 'Vacant':
  exit()
  
print(r, flush=True)

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

seeking_range =[0,N-1]
seat_condition = ["" for _ in range(N)]

print(0, flush = True)
seat_condition[0] = input()


if seat_condition[0] != "Vacant":
    for n in range(19):
        next_target = sum(seeking_range)//2
        if seeking_range[0] == N-2:
            next_target = N-1
        print(next_target, flush = True)
        seat_condition[next_target] = input()
        
    
        if "Vacant" in seat_condition:
            break

        if (next_target - seeking_range[0] +1) % 2 == 0:

            if (seat_condition[seeking_range[0]] == seat_condition[next_target]):
                seeking_range[1] = next_target
            else:
                seeking_range[0] = next_target

        else:

            if (seat_condition[seeking_range[0]] == seat_condition[next_target]):
                seeking_range[0] = next_target
            else:
                seeking_range[1] = next_target

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

print(0)
nex=input()
if nex=="Vacant":
    exit()
nleft=0
left=nex
print(N-1)
nex=input()
if nex=="Vacant":
    exit()
nright=N-1
right=nex

for i in range(20):
    nmid=(nright+nleft)//2
    print(nmid)
    nex=input()
    if nex=="Vacant":
        exit()
    mid=nex
    flag=True
    if nleft%2!=nmid%2:
        if left==mid:
            right=mid
            nright=nmid
            flag=False
    else:
        if left!=mid:
            right=mid
            nright=nmid
            flag=False
    if flag:
        left=mid
        nleft=nmid

Solution (Python):
n = int(input())
l = 0
r = n - 1
print(l)
s_l = str(input())
if s_l == 'Vacant':
    exit()
while abs(l - r) > 1:
    m = (l + r) // 2
    print(m)
    s_m = str(input())
    if s_m == 'Vacant':
        exit()
    else:
        if (m - l) % 2:
            if s_m != s_l:
                l = m
                s_l = s_m
            else:
                r = m
                s_r = s_m
        else:
            if s_m != s_l:
                r = m
                s_r = s_m
            else:
                l = m
                s_l = s_m
else:
    print(r)
    s = str(input())

Solution (Python):
def main():
    N = int(input())
    print(0, flush=True)
    s = input()
    if s == 'Vacant':
        exit()
    ans = [''] * N
    ans[0] = s
    pre = 0
    left = 0
    right = N
    while True:
        mid = (right + left) // 2
        print(mid, flush=True)
        s = input()
        ans[mid] = s
        if s == 'Vacant':
            exit()
        cnt = abs(mid - pre)
        if cnt % 2 == 0:
            if ans[pre] == ans[mid]:
                
                if pre > mid:
                    right = mid
                else:
                    left = mid
            else:
                
                if pre > mid:
                    left = mid
                else:
                    right = mid
        else:
            if ans[pre] == ans[mid]:
                
                if pre > mid:
                    left = mid
                else:
                    right = mid
            else:
                
                if pre > mid:
                    right = mid
                else:
                    left = mid
        pre = mid

        


if __name__ == "__main__":
    main()

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

print(0)
s0 = input().strip()
if s0 == "Vacant":
  exit()


def is_ok(arg):
  print(arg)
  s = input().strip()
  if s ==  "Vacant":
    exit()
  if (arg%2==0 and s==s0) or (arg%2!=0 and s!=s0):
    return True
  else:
    return False

def meguru_bisect(ng, ok):
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return print(ng)


ok = 0
ng = N-1
meguru_bisect(ng,ok)

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):
def printf(i):
  print(i,flush=True)
n=int(input())
printf(0)
ls=input()
if ls=='Vacant':
  exit()
l=0
r=n
while True:
  m=(l+r)//2
  printf(m)
  ch=input()
  if ch=='Vacant':
    exit()
  if ls==ch:
    if (m-l)%2:
      r=m
    else:
      l=m
  else:
    if (m-l)%2:
      l=m
      ls=ch
    else:
      r=m

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

lb, ub = 0, n
print(lb, flush=True)
s = str(input())
if s == 'Vacant':
    exit()
for i in range(19):
    mid = (lb + ub) // 2
    print(mid, flush=True)
    t = str(input())
    if t == 'Vacant':
        exit()
    if (mid - lb) % 2 == 0 and s == t:
        lb = mid
    elif (mid - lb) % 2 == 0 and s != t:
        ub = mid
    elif s == t:
        ub = mid
    else:
        lb, s = mid, t

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



def check(i,s,s0):
    if i%2 == 0:
        if s == s0:
            return True
        else:
            return False
    else:
        if s != s0:
            return True
        else:
            return False

N = I()
print(0)
sys.stdout.flush()
s0 = str(input())
if s0 == 'Vacant':
    exit()

print(N-1)
sys.stdout.flush()
s1 = str(input())
if s1 == 'Vacant':
    exit()

ok = N-1
ng = 0
while True:
    mid = (ok+ng)//2
    print(mid)
    sys.stdout.flush()
    s = str(input())
    if s == 'Vacant':
        exit()
    flag = check(mid,s,s0)
    if flag:
        ng = mid
    else:
        ok = mid

Solution (Python):
n = int(input())
a,b = 0, n
print(a,flush=True)
s = str(input())
if s == 'Vacant':
        exit()
for i in range(19):
    check = (a+b) // 2
    print(check,flush=True)
    t = str(input())
    if t == 'Vacant':
        exit()
    if (check-a) % 2 == 0 and s == t:
        a = check
    elif (check-a) % 2 == 0 and s != t:
        b = check
    elif s == t:
        b = check
    else:
        a,s = check,t

Solution (Python):
def solve(bi, ei, bs):
    mid = (bi+ei)//2
    print(mid, flush=True)
    s = input()
    if s=='Vacant':
        exit(0)
    elif (s==bs)^((mid-bi)%2):
        solve(mid, ei, s)
    else:
        solve(bi, mid, bs)

n = int(input())
print(0, flush=True)
s = input()
if s=='Vacant':
    exit(0)
solve(0, n, s)

Solution (Python):
n = int(input())
l, r = 0, n-1
print(0, flush=True)
l_s = input()
if l_s == "Vacant":
  exit()
print(n-1, flush=True)
l_t = input()
if l_t == "Vacant":
  exit()
while True:
  mid = (l+r)//2
  print(mid, flush=True)
  t = input()
  if t == "Vacant":
    exit()
  if ((mid-l)%2 and l_s==t) or ((mid-l)%2==0 and l_s!=t):
    r = mid
  else:
    l = mid
    l_s = t

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    l = 0
    r = n
    print(0)
    la = input()
    if la == "Vacant":
        exit()
    ra = la
    while True:
        mid = l+(r-l)//2
        print(mid)
        ma = input()
        if ma == "Vacant":
            exit()
        elif (ma == la and (mid-l)%2 == 0) or ((not ma == la) and (mid-l)%2 == 1):
            l = mid
            la = ma
        else:
            r = mid
            ra = ma

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys

n = int(input())
print(0)
sys.stdout.flush()
ls = input()
if ls == 'Vacant':
    exit()
print(n - 1)
sys.stdout.flush()
if input() == 'Vacant':
    exit()
l = 0
r = n - 1
while l != r - 1:
    mid = (l + r) // 2
    if mid % 2 == 1:
        mid += 1
    if mid == r:
        mid -= 1
    print(mid)
    sys.stdout.flush()
    nex = input()
    if nex == 'Vacant':
        exit()

    if ls == nex:
        l = mid
    else:
        r = mid

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

def main():
    N = int(input())
    print(0)
    flush()
    sex = input()
    if sex == "Vacant":
        exit()

    even_sex = sex
    def isOK(mid):
        print(mid)
        flush()
        sex = input()
        if sex == "Vacant":
            exit()
        elif mid%2 == 0:
            if even_sex == sex: return True
            else:return False
        else:
            if even_sex != sex: return True
            else: return False
        
    def bin_search():
        l = 0
        r = N
        while l!=r:
            mid = l + (r-l)//2
            if isOK(mid):
                l = mid
            else:
                r = mid
                
    bin_search()

if __name__ == "__main__":
    main()