Draft solution of IPSC 2018 K - easy subprob.

ipsc2018k1.py

import sys
sys.setrecursionlimit(100000)

def gcd(x, y):
	return y if x%y == 0 else gcd(y, x%y)

def binary_search(s, e, a, b): # a/b
	# 0: left / 1: right
	m = s + e
	if a == 0:
		return ''
	if a*(s*m) > b: # a/b > 1/(s*m)
		c = a*s*m - b
		d = b*s*m
		g = gcd(c, d)
		c //= g
		d //= g
		return '1' + binary_search(m, e, c, d)
	elif a*(s*m) < b:
		return '0' + binary_search(s, m, a, b)
	else:
		return ''

print(binary_search(1, 1, 1, 3)) # '0'
print(binary_search(1, 1, 1, 4)) # '00'
print(binary_search(1, 1, 3, 5)) # '10'
print(binary_search(1, 1, 4, 11)) # '0100'

# use pell's equation to represent 1/sqrt(2):
print(binary_search(1, 1, 1111984844349868137938112, 1572584048032918633353217)) # '11001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001'