GCJ 2013 R1A “Bullseye” O(1) solution

https://code.google.com/codejam/contest/2418487/dashboard
This is only possible because of Python’s arbitrary precision arithmetic, which is a serious lack on C++ Standard Library. The solution follows AL series summation methods, after sleeping through the actual competition it took me a few days to come up with this :D.

import math
import sys
from decimal import *

getcontext().rounding = ROUND_HALF_UP
getcontext().prec = 100

def revens(r):
	if r==0:
		return 0
	else:
		return (2*(r//2-1)+1)*((r//2-1)+1);

def rodds(r):
	if r==1:
		return 0
	else:
		return (r//2)*(2*(r//2)+1)

def proc(r,t):
	if r%2==0:
		ff= (Decimal(-3)+ Decimal(1+8*(revens(r)+t)).sqrt() ) /Decimal(4)
		rr = ff - Decimal(r//2)+Decimal(1)
	else:
		ff = (Decimal(-1)+ Decimal(1+8*(rodds(r)+t)).sqrt() ) /Decimal(4)
		rr = ff - Decimal(r//2)
	return rr

sys.stdin.readline()
case=1
for line in sys.stdin.readlines():
	line = line.strip()
	arr = line.split()
	print("Case #%d: %d"%(case,proc(int(arr[0]),int(arr[1]))))
	case=case+1
Advertisements