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