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

Solution (Python):

N = int(input())

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

l, r = 0, N
while True:
    m = (l + r) // 2
    print(m, flush=True)
    w1 = input()
    if w1 == 'Vacant':
        break
    if m % 2 == (w0 != w1):
        l = m
    else:
        r = m

Solution (Python):
N = int(input())
ans = float('inf')
print(0)
s = input()
if s == "Male":
	pre = 1
elif s == "Female":
	pre = 0
else:
	ans = 0

if ans == 0:
	exit(0)

ran = [0,N-1]
for i in range(19):	
	n = (ran[1] - ran[0]) // 2
	print(ran[0] + n)
	s = input()
	if s == "Male":
		flg = 1
	elif s == "Female":
		flg = 0
	else:
		exit(0)

	if (pre + n) % 2 != flg:
		ran[1] = ran[0] + n - 1
	else:
		ran[0] = ran[0] + n + 1
		pre = (flg + 1) % 2

Solution (Python):




def solve(il, ir, l, r):
    ni = il + (ir - il) // 2
    print(ni)

    s = input()
    if s == 'Vacant':
        return
    elif (s == l and (ni - il) % 2 == 1) or (s != l and (ni - il) % 2 == 0):  
        solve(il, ni, l, s)
    else:
        solve(ni, ir, s, r)


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

    print(0)

    s = input()
    if s == 'Vacant':
        return

    solve(0, N, s, s)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
l = 0
s = []
start = [0]
end = [n]
check = 1

for i in range(20):
	print(l)
	stemp = str(input())
	s.append(stemp)
	if stemp == 'Vacant':
		break
	elif i!=0:
		if check == 1:
			if s[i-1] == s[i]:
				start[0] = l
				if ((end[0]-start[0])//2)%2==0:
					l = start[0]+(end[0]-start[0])//2
				else:
					l = start[0]+(end[0]-start[0])//2+1
				
			else:
				end[0] = l
				if ((end[0]-start[0])//2)%2==0:
					l = start[0]+(end[0]-start[0])//2
				else:
					l = start[0]+(end[0]-start[0])//2+1
				check = check*-1

		elif check == -1:
			if s[i-1] == s[i]:
				end[0] = l
				if ((end[0]-start[0])//2)%2==0:
					l = start[0]+(end[0]-start[0])//2
				else:
					if abs((end[0]-start[0])) == 2:
						l = start[0]+(end[0]-start[0])//2
					else:
						l = start[0]+(end[0]-start[0])//2-1
				
			else:
				start[0] = l
				if ((end[0]-start[0])//2)%2==0:
					l = start[0]+(end[0]-start[0])//2
				else:
					l = start[0]+(end[0]-start[0])//2+1
				check = check*-1
	else:
		if (n//2)%2==0:
			l = l+n//2
		else:
			l = l+(n//2)+1

Solution (Python):
n = int(input())
nn = (n + 1) // 2
s = [0]*n
print(0)
s[0] = input()
if s[0] == "Vacant":
    exit()
print(n-1)
s[n-1] = input()
if s[n-1] == "Vacant":
    exit()
ll = 0
hh = nn-1
while hh - ll > 1:
    l = ll*2
    h = hh*2
    ii = (ll + hh) // 2
    i = ii*2
    print(i)
    s[i] = input()
    if s[i] == "Vacant":
        exit()
    elif s[i] != s[l]:
        hh = ii
    else:
        ll = ii
print(ll+hh)

Solution (Python):

import math
import sys

def isBetween(i1, i2, res1, res2):
    return (i1 % 2 == i2 % 2) != (res1 == res2)

def search(s_range, isLeft, result):
    half = s_range[0] + math.floor((s_range[1] - s_range[0])/2)
    print(half)
    res = input()

    if res == 'Vacant':
        return

    if isLeft:
        if isBetween(s_range[0]-1, half, result, res):
            search((s_range[0], half-1), False, res)
        else:
            search((half+1, s_range[1]), True, res)
    else:
        if isBetween(half, s_range[1]+1, res, result):
            search((half+1, s_range[1]), True, res)
        else:
            search((s_range[0], half-1), False, res)


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

    print(0)
    res = input()

    s_range = (1, N-1)
    search(s_range, True, res)

main()

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

    if seat%2==0:
        if 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
            
    else:
        if 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):
    m_of_f(seat_check, n_max, n_min, seat_zero)

Solution (Python):

import sys

def inpl(): return tuple(map(int, input().split()))

def ismale(S):
    if S == "Male":
        return 1
    elif S == "Female":
        return 0
    else:
        exit()

N = int(input())
print(0)
sys.stdout.flush()

c0 = ismale(input())
w = c0

C = [0 for _ in range(N)]

L = 0
R = N - 1
post = (R + L)//2
while True:
    print(post)
    sys.stdout.flush()
    
    if post % 2 == 1:
        c = ismale(input())
        if c != w:
            L = post + 1
        else:
            R = post - 1
    else:
        c = ismale(input())
        if c != w:
            R = post
        else:
            L = post

    if R - L == 2:
        print((R+L+1)//2)
        sys.stdout.flush()
        c = ismale(input())
        print(R)
        sys.stdout.flush()
        c = ismale(input())
        print(L)
        sys.stdout.flush()
        c = ismale(input())
    else:
        post = (R + L)//2

Solution (Python):


import sys

n = int(raw_input())
print 0
sys.stdout.flush()
status_0 = raw_input()
start = 0
end = n-1
check = end
i = 1
if status_0 == "Vacant":
    pass
else:
    while 1:
        print check
        sys.stdout.flush()
        status = raw_input()
        if status == "Vacant":
            break
        elif status == status_0:
            if check % 2 == 0:
                start = check
            else:
                end = check
        else:
            if check % 2 == 0:
                end = check
            else:
                start = check
        check = start+(end-start)/2

quit()

Solution (Python):
def m_of_f(l,m,m_min,fm):
    global k
    global n
    global n_min

    print(l)

    s=input()

    if l%2==0:
        if s==fm:
            n_min=l
            l=int(0.5*(m+l))
            k=l
            
        else :
            n=l
            l=int(0.5*(l+m_min))
            k=l
            
    else:
        if s!=fm:
            n_min=l
            l=int(0.5*(m+l))
            k=l
        else :
            n=l
            l=int(0.5*(l+m_min))
            k=l
n=int(input())
nn=n
n_min=0



print(0)
sss=input()
k=int(0.5*n)

for i in range(19):
    m_of_f(k,n,n_min,sss)

Solution (Python):
import sys
def res(N,bia,s0):
  if N%4==1:
    N2=int(N/2)+1
  else:
    N2=int(N/2)
  print(N2+bia)
  sn=input()
  if sn=='Vacant':
    sys.exit()
  elif sn==s0:
    res(N2,bia,s0)
  else:
    if N==3:
      print(bia+2)
      sys.exit()
    res(N-N2+1,N2+bia-1,s0)
N=int(input())
print(0)
s0=input()
if s0=='Vacant':
  sys.exit()
res(N,0,s0)

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

right = n
left = 0

print(0)
first = input()
state = first

cnt = 0
while True:
    cnt += 1
    if state == "Vacant":
        __import__("sys").exit()

    target = left + (right - left) // 2
    target = max(target, 1)

    print(target)
    state = input()

    if (target & 1 and state != first) or (not target & 1 and state == first):
        left = target
    else:
        right = target

    if left == right:break

Solution (Python):
m = 'Male'
f = 'Female'
v = 'Vacant'

N = int(input())
x = 0
y = N
cnt = 1
print(0)
p_bef = 0
h_bef = input()
if h_bef == v:
	exit()
while cnt < 50:
	p = (x+y+1)//2
	print(p)
	h = input()
	if h == v:
		break
	mod = 0 if h_bef == h else 1
	if (p-x) % 2 == mod:
		x = p
		h_bef = h
	else:
		y = p
	cnt += 1
exit()

Solution (Python):
import sys, math

N = int(input())
low = 0
high = N - 1

print(0)
start = input()
tmp = math.ceil((high + low) / 2)
print(tmp)

while True:
    s = input()
    if s == 'Vacant':
        break
    else:
        if (tmp % 2 == 0) ^ (s == start):
            high = tmp
        else:
            low = tmp
        tmp = math.ceil((high + low) / 2)
        print(tmp)

sys.stdout.flush()

Solution (Python):
import sys, math

N = int(input())
low = 0
high = N - 1

print(0)
start = input()
tmp = math.ceil((high + low) / 2)
print(tmp)

while True:
    i = input()
    if i == 'Vacant':
        break
        
    else:
        if (tmp % 2 == 0 and i == start) or (tmp % 2 != 0 and i != start):
            low = tmp
        else:
            high = tmp
        
        tmp = math.ceil((high + low) / 2)
        print(tmp)

sys.stdout.flush()

Solution (Python):
n = int(input())
a = {}
print(0)
a1 = input()
a.setdefault(0, a1)
a.setdefault(n, a1)
if a1 == "Vacant":
    pass
else:
    start = 0
    end = n
    for i in range(19):
        question = start + (end - start) // 2
        print(question)
        answer = input()
        a.setdefault(question, answer)
        if answer == "Vacant":
            break
        if (question - start) % 2 == 0 and a[start] == a[question]:
            start = question
        if (question - start) % 2 == 0 and a[start] != a[question]:
            end = question
        if (question - start) % 2 == 1 and a[start] == a[question]:
            end = question
        if (question - start) % 2 == 1 and a[start] != a[question]:
            start = question

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

q = 0
res = []
for i in range(20):
    print(q)
    s = input()
    if s[0] == 'V':
        exit()
    res.append((q,s[0]))
    res.sort()
    if len(res) == 1:
        q = N//2
        continue
    for (i1,g1),(i2,g2) in zip(res,res[1:]):
        if i2-i1 == 1: continue
        if (i2-i1)%2 == int(g1==g2):
            q = (i2+i1)//2
            break
    else:
        q = (res[-1][0] + N + 1)//2

Solution (Python):
import sys, math

N = int(input())
genders = ['Male', 'Female']
low = 0
high = N - 1

tmp_seat = low
print(tmp_seat)

start = input()

tmp_seat = math.ceil((high + low) / 2)
print(tmp_seat)

while True:
    i = input()
    if i == 'Vacant':
        break
    else:
        if (tmp_seat % 2 == 0 and i == start) or (tmp_seat % 2 != 0 and i != start):
            low = tmp_seat   
        else:
            high = tmp_seat
        
        tmp_seat = math.ceil((high + low) / 2)
        print(tmp_seat)
            
sys.stdout.flush()

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

def query(n):
  print(n)
  ret = input()
  if ret == 'Vacant':
    exit()
  return ret

low = 0
high = N
lowseat = query(low)
while True:
  mid = math.ceil((low + high) / 2)
  midseat = query(mid)
  if (mid - low) % 2 == 0:
    
    if lowseat != midseat:
      high = mid
    else:
      low = mid
      lowseat = midseat
  else:
    
    if lowseat == midseat:
      high = mid
    else:
      low = mid
      lowseat = midseat

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

def search(a,b,a_in,b_in):
    c=(a+b)//2
    print(c,flush=True)
    c_in=input()
    if(c_in=='Vacant'):
        return
    if(((a-c)%2==0) ^ (a_in==c_in)):
        
        search(a,c,a_in,c_in)
    else:
        search(c,b,c_in,b_in)

a=0
print(a,flush=True)

a_in=input()

if(a_in!='Vacant'):
    search(0,n,a_in,a_in)

Solution (Python):

import sys
def guess(i):
    print(int(i))
    sys.stdout.flush()
    s=input()
    if s=="Male":
        return 0
    if s=="Female":
        return 1
    if s=="Vacant":
        exit(0)

n=int(input())

a=guess(0)
b=guess(n-1)
hi=n-1
lo=0

for i in range(18):
    mid=(hi+lo)//2
    c=guess(mid)
    if (c-a)%2==(mid-lo)%2:
        lo=mid
        a=c
    else:
        hi=mid
        b=c

Solution (Python):

import sys

N = int(input())
left = 0
right = N-1
ans_left = ''
ans_right = ''

cnt = 0

print(0)
cnt += 1
s = input()
ans_left = s

if s != "Vacant":
    print(N-1)
    cnt += 1
    s = input()
    ans_right = s


    
while s != "Vacant" and cnt < 20:
    
    
    mid = (left + right) // 2
    print(mid)
    cnt += 1
    s = input()
    
    m = (mid - left) % 2
    if m == 0:
        if ans_left != s:
            right = mid
            ans_right = s
        else:
            left = mid
            ans_left = s
    else:
        if ans_left == s:
            right = mid
            ans_right = s
        else:
            left = mid
            ans_left = s

Solution (Python):

def solve(N):
    print(0, flush=True)
    answer = input()[0]
    if answer == "V":
        return
    st = 0
    stc = answer
    ed = N
    edc = answer
    for i in range(20):
        x = (st + ed) // 2
        print(x, flush=True)
        answer = input()[0]
        if answer == "V":
            return
        if (x - st) % 2 == 0 and stc != answer:
            ed = x
            edc = answer
            continue
        if (x - st) % 2 == 1 and stc == answer:
            ed = x
            edc = answer
            continue
        if (ed - x) % 2 == 0 and edc != answer:
            st = x
            stc = answer
            continue
        if (ed - x) % 2 == 1 and edc == answer:
            st = x
            stc = answer
            continue

    return 0

if __name__ == "__main__":
    N = int(input())
    solve(N)

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

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

a = 0
b = N
ga = ask(a)
gb = ga

while a < b:
  m = (a+b)//2
  gm = ask(m)

  parity_am = (m-a)%2 == 0
  parity_mb = (b-m)%2 == 0

  ram = (ga==gm) == parity_am
  rmb = (gm==gb) == parity_mb
  if ram:
    a = m
    ga = gm
  else:
    b = m
    gb = gm

ask(a)

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

MALE = 1
FEMALE = 2
UNKNOWN = -1

states = [UNKNOWN for _ in range(N)]


def query(i):
    i %= N
    if states[i] != UNKNOWN:
        return states[i]
    print(i)
    state = input()
    if state == 'Vacant':
        sys.exit()
    elif state == 'Male':
        states[i] = MALE
    elif state == 'Female':
        states[i] = FEMALE
    else:
        return query(i)
    return states[i]


imin = 0
imax = N - 1
smin = query(imin)
smax = query(imax)

while True:
    imid = (imax + imin) // 2
    smid = query(imid)

    minside = False
    if smid == smin and (imid - imin) % 2 == 1:
        minside = True
    if smid != smin and (imid - imin) % 2 == 0:
        minside = True

    if minside:
        imax = imid
        smax = smid
    else:
        imin = imid
        smin = smid

Solution (Python):
n = int(input())
print(0)
sl = input()
if sl == 'Vacant':
    exit()
l, r = 0, n - 1
pm = -1
while True:
    
    m = (l + r) // 2
    if pm == m:
        m += 1
    print(m)
    sm = input()
    if sm == 'Vacant':
        break
    if sl == sm:
        if (m - l) & 1:
            r = m
        else:
            l = m
            sl = sm
    else:
        if (m - l) & 1:
            l = m
            sl = sm
        else:
            r = m
    pm = m

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write
flush = sys.stdout.flush

def query(i):
    write("%d\n" % i)
    flush()
    res = readline()
    if res == 'Vacant\n':
        exit(0)
    return ["Male\n", "Female\n"].index(res)

N = int(readline())

init = query(0)
left = 0; right = N
while 1:
    mid = (left + right) // 2
    res = query(mid)
    if res^init == mid%2:
        left = mid
    else:
        right = mid
print(left)

Solution (Python):
n = int(input())
def query(b, e, t):
    m = (e+b+1)//2
    print(m)
    res = input()[0]
    if ((m-b)%2 == 0) == (res == t):
        query(m, e, res)
    else:
        query(b, m-1, t)
print(0)
query(0, n-1, input()[0])

Solution (Python):
from sys import stdout
def Q(x):
    print x
    stdout.flush()
    r = raw_input()
    if r[0] == 'V':
        quit()
    elif r[0] == 'M':
        return 1
    else:
        return 0
l = 0
r = int(raw_input())
a = b = Q(l)
while 1:
    m = (l + r) / 2
    c = Q(m)
    if (m - l) % 2 == a ^ c:
        l, r, a, b = m, r, c, b
    else:
        l, r, a, b = l, m, a, c

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

    print(0,flush=True)
    s = input()
    if s=="Vacant": return 0
    cap = 0
    if s=="Female": cap = 1

    lo = 0
    hi = n
    while True:
        mid = (hi+lo)//2
        print(mid, flush=True)
        s = input()

        if s=="Vacant": return 0
        gen = 0
        if s=="Female": gen = 1

        if (cap+mid)%2 == gen:
            lo = mid
        else:
            hi = mid

main()