Skip to content

Instantly share code, notes, and snippets.

@xjcl
Last active Apr 26, 2021
Embed
What would you like to do?
Google Code Jam -- Blindfolded Bullseye -- Solution in Python
# usage: (python3 a.py < a.in) > a.out
import time, sys, inspect, platform
print = lambda *a, **k: __builtins__.print(str(inspect.currentframe().f_back.f_lineno)+':',
*a, file=sys.stderr, **k) if platform.node() in ['surfux', 'ssd'] else ...
class EndTestCase(Exception): pass
#---------------------------------------------
t, a, b = [int(x) for x in input().split()]
def guess(x, y):
__builtins__.print(str(x) + ' ' + str(y))
answer = input()
print(answer, 'for input', x, y)
if answer == 'CENTER':
raise EndTestCase
return answer == 'HIT'
# Search on the interval [lo,hi) vvvv
# Return first index where test_func is True -> [False..False, True..True]
# This will fail when the list is all False
def bin_search(lo, hi, test_func):
print('Calling bin_search with ', lo, hi)
if lo == hi - 1:
return lo
mid = (hi+lo-1)//2
if test_func(mid):
return bin_search(lo, mid + 1, test_func)
else:
return bin_search(mid + 1, hi, test_func)
def get_startpos():
for x,y in [(-10**9//2,0), (0,-10**9//2), (0,0), (0,10**9//2), (10**9//2,0)]:
if guess(x,y):
return (x,y)
def case():
startpos = get_startpos()
print(startpos)
x_lo = bin_search(-10**9, startpos[0]+1, lambda x: guess(x, startpos[1]) )
x_hi = bin_search(startpos[0], 10**9+2, lambda x: not guess(x, startpos[1]) ) - 1
y_lo = bin_search(-10**9, startpos[1]+1, lambda y: guess(startpos[0], y) )
y_hi = bin_search(startpos[1], 10**9+2, lambda y: not guess(startpos[0], y) ) - 1
print('************', x_lo, x_hi, y_lo, y_hi)
x_avg = (x_lo + x_hi) // 2
y_avg = (y_lo + y_hi) // 2
guess(x_avg, y_avg)
raise Exception('this line should never be reached')
for _ in range(t):
try:
case()
except EndTestCase:
pass
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment