Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import multiprocessing
- import cPickle
- import time
- import bisect
- import math
- from files import *
- """
- Things yet to do:
- """
- BABY = 0
- SMALL = 1
- LARGE = 2
- PSMALL = 3
- PLARGE = 4
- def doit(preprocess, readinput, solve, MultiCore = True, Verify = False, Input = None, Filename = None, Problem = "A", Attempt = 0, SingleCase = False):
- start_time = time.time()
- if Input == None:
- if Filename == None:
- print "Input Filename Not specified."
- return
- INPUTNAME = Filename
- else:
- INPUTNAME = Problem + "_baby.in"
- if Input == SMALL: INPUTNAME = Problem + "-small-attempt" + str(Attempt) + ".in"
- if Input == LARGE: INPUTNAME = Problem + "-large.in"
- if Input == PSMALL: INPUTNAME = Problem + "-small-practice.in"
- if Input == PLARGE: INPUTNAME = Problem + "-large-practice.in"
- OUTPUTNAME = INPUTNAME[:INPUTNAME.find(".")] + ".out"
- Input = File(INPUTNAME, "r")
- Correct = None
- if Verify == True:
- try:
- Output = File(OUTPUTNAME, "r")
- Correct = Output.readall()
- except IOError:
- print "Verification not possible - output file does not exist. Fall back to normal mode."
- Verify = False
- Output = File(OUTPUTNAME, "w")
- else:
- Output = File(OUTPUTNAME, "wb")
- PREPNAME = Problem + ".prep"
- try:
- pfile = open(PREPNAME, "rb")
- Prep = cPickle.load(pfile)
- pfile.close()
- print "Loaded preprocessed information from file"
- except IOError:
- Prep = preprocess()
- if Prep <> None:
- pfile = open(PREPNAME, "wb")
- cPickle.dump(Prep, pfile, 2)
- pfile.close()
- print "Saved preprocessed information to file"
- if SingleCase == True:
- n_cases = 1
- else:
- n_cases = Input.readint()
- Problems = []
- # Just reading input
- for _ in range(n_cases):
- Problems.append(readinput(Input))
- AllCorrect = True
- if MultiCore:
- pool = multiprocessing.Pool(processes = 6)
- Result = [pool.apply_async(solve, [p, Prep]) for p in Problems]
- for n in range(n_cases):
- if MultiCore:
- Solution = Result[n].get()
- else:
- Solution = solve(Problems[n], Prep)
- sline = "Case #" + str(n+1) + ": " + str(Solution)
- print sline
- if not Verify:
- Output.write(sline + "\n")
- else:
- for line in split(sline, "\n"):
- if len(Correct) == 0 or line.rstrip("\n") <> Correct[0].rstrip("\n"):
- print "MISMATCH: ", line,
- AllCorrect = False
- if len(Correct) > 0: print Correct[0]
- else: print ""
- if len(Correct) > 0: Correct.pop(0)
- TOT = (time.time() - start_time) / (n + 1) * n_cases
- if TOT > 120:
- print "Running over two minutes by:", int (TOT - 120), "seconds"
- print time.time() - start_time, "seconds"
- if Verify and AllCorrect == False:
- print "VERIFICATION FAILED - ERRORS WERE FOUND IN SOLUTION"
- return
- Primes = None
- def frange(x, y, jump):
- while x < y:
- yield x
- x += jump
- def getPrimes(A, B):
- global Primes
- """get primes between A and B inclusive"""
- if Primes == None:
- pfile = open("Primes.prep", "rb")
- Primes = cPickle.load(pfile)
- pfile.close()
- if B > 15485863:
- print "Sorry, no data on primes so large"
- quit()
- S = bisect.bisect_left(Primes, A)
- E = bisect.bisect_left(Primes, B + 1)
- return Primes[S:E]
- def ncr(n, r):
- r = min(r, n-r)
- if r == 0: return 1
- if r < 0: return 0
- num = reduce(mul, xrange(n, n-r, -1))
- denom = reduce(mul, xrange(1, r+1))
- return num/denom
- def memoize(f):
- cache= {}
- def memf(*x):
- if x not in cache:
- cache[x] = f(*x)
- return cache[x]
- return memf
- def Transpose(M):
- X = len(M)
- Y = len(M[0])
- A = []
- for y in range(Y):
- B = [0] * X
- for x in range(X):
- B[x] = M[x][y]
- A.append(B)
- return A
- def bin_search_max(function, search_from, search_to, *args):
- """
- function - function to test - must return True when result is OK.
- search_from - search from where (integer!)
- search_to - search to where (integer!)
- """
- while search_from <> search_to:
- guess = (search_from + search_to) / 2 + 1
- if function(guess, *args):
- search_from = guess
- else:
- search_to = guess - 1
- return search_from
- def bin_search_max_float(function, search_from, search_to, precision, *args):
- """
- function - function to test - must return True when result is OK.
- search_from - search from where (integer!)
- search_to - search to where (integer!)
- """
- while abs(search_from - search_to) > precision:
- guess = (search_from + search_to) / 2.0
- if function(guess, *args):
- search_from = guess
- else:
- search_to = guess
- return search_from
- def bin_search_min_float(function, search_from, search_to, precision, *args):
- """
- function - function to test - must return True when result is OK.
- search_from - search from where (integer!)
- search_to - search to where (integer!)
- """
- while abs(search_from - search_to) > precision:
- guess = (search_from + search_to) / 2.0
- if function(guess, *args):
- search_to = guess
- else:
- search_from = guess
- return search_from
- def bin_search_min(function, search_from, search_to, *args):
- """
- function - function to test - must return True when result is OK.
- search_from - search from where (integer!)
- search_to - search to where (integer!)
- """
- while search_from <> search_to:
- guess = (search_from + search_to) / 2
- if function(guess, *args):
- search_to = guess
- else:
- search_from = guess + 1
- return search_from
- def bin_search(function, search_result, search_from, search_to, precision, *args):
- """
- function - function to test
- search_result - what to look for (which number)
- search_from - search from where
- search_to - search to where
- precision - precision for comparison to test result
- """
- W = search_to - search_from
- step = W / 4.0
- initial = W / 2.0 + search_from
- s = function(initial, *args)
- while abs(step) > precision:
- if s > search_result and step > 0:
- step = - step / 2
- if s < search_result and step < 0:
- step = - step / 2
- initial = initial + step
- s = function(initial, *args)
- return initial
- def square_matrix_multiply(a, b):
- s = len(a)
- r = []
- for x in range(s):
- r.append([0] * s)
- for y in range(s):
- for t in range(s):
- r[x][y] += (a[x][t] * b[t][y])
- r[x][y] = r[x][y]
- return r
- def fastpower(m, x, p):
- """return a**b % q"""
- val = x
- mult = x
- p -= 1
- while p > 0:
- odd = p & 1 # bitwise and
- if odd == 1:
- val = m(val, mult)
- p -= 1
- if p == 0:
- break
- mult = m(mult, mult)
- p = p >> 1 # bitwise divide by 2
- return val
- def feq(a, b):
- return fabs(a-b) < 1e-8
- def next_permutation(L):
- B = len(L) - 1
- while L[B] <= L[B-1]:
- B = B - 1
- if (B == 0):
- return sorted(L)
- b = B
- for x in range(B, len(L)):
- if L[b] > L[x] and L[x] > L[B-1]:
- b = x
- (L[b], L[B - 1]) = (L[B - 1], L[b])
- L = L[:B] + sorted(L[B:])
- return L
- def semi_circle_segment(x0, x1, R):
- def integral(x, R):
- h = R - x
- return (R**2*acos((R-h)/R) - (R-h)*sqrt(2*R*h-h**2))/2
- return - integral(x1, R) + integral(x0, R)
- def isqrt(x):
- if x < 0:
- raise ValueError('square root not defined for negative numbers')
- n = int(x)
- if n == 0:
- return 0
- a, b = divmod(n.bit_length(), 2)
- x = 2**(a+b)
- while True:
- y = (x + n//x)//2
- if y >= x:
- return x
- x = y
- class File:
- def __init__(self, filename, mode):
- self.handle = open(filename, mode)
- self.cursor = 0
- self.filename = filename
- self.mode = mode
- if mode == "r":
- self.lines = self.handle.readlines()
- def __del__(self):
- self.handle.close()
- def readint(self):
- a = int(self.lines[self.cursor])
- self.cursor += 1
- return a
- def readall(self):
- return self.lines
- def readbinary(self):
- self.handle.close()
- self.handle = open(self.filename, "rb")
- return self.handle.read()
- def readints(self):
- ints = self.lines[self.cursor]
- ints = strip(ints, "\n")
- ints = strip(ints, " ")
- while " " in ints:
- ints = ints.replace(" ", " ")
- ints = ints.split(" ")
- for a in range(len(ints)):
- ints[a] = int(ints[a])
- self.cursor += 1
- return ints
- def readfloats(self):
- ints = self.lines[self.cursor]
- ints = strip(ints, "\n")
- ints = ints.split(" ")
- for a in range(len(ints)):
- ints[a] = float(ints[a])
- self.cursor += 1
- return ints
- def readstring(self):
- a = self.lines[self.cursor]
- a = strip(a, "\n")
- self.cursor += 1
- return a
- def readstrings(self):
- a = self.lines[self.cursor]
- a = strip(a, "\n")
- a = a.split(" ")
- self.cursor += 1
- return a
- def write(self, line):
- self.handle.write(line)
- return
- def writeint(self, number):
- self.handle.write(str(number))
- return
- def writefloat(self, fl, after):
- self.handle.write(("%." + str(after) + "f") % fl)
- return
- def nextline(self):
- self.handle.write("\n")
- return
- """Matrix = numpy.array(Matrix, dtype = numpy.int64)"""
- class UnionFind:
- def __init__(self):
- '''\
- Create an empty union find data structure.'''
- self.num_weights = {}
- self.parent_pointers = {}
- self.num_to_objects = {}
- self.objects_to_num = {}
- self.unique = 0
- def insert_objects(self, objects):
- '''\
- Insert a sequence of objects into the structure. All must be Python hashable.'''
- for object in objects:
- self.find(object);
- def find(self, object):
- '''\
- Find the root of the set that an object is in.
- If the object was not known, will make it known, and it becomes its own set.
- Object must be Python hashable.'''
- if not object in self.objects_to_num:
- obj_num = len(self.objects_to_num)
- self.num_weights[obj_num] = 1
- self.objects_to_num[object] = obj_num
- self.num_to_objects[obj_num] = object
- self.parent_pointers[obj_num] = obj_num
- self.unique += 1
- return object
- stk = [self.objects_to_num[object]]
- par = self.parent_pointers[stk[-1]]
- while par != stk[-1]:
- stk.append(par)
- par = self.parent_pointers[par]
- for i in stk:
- self.parent_pointers[i] = par
- return self.num_to_objects[par]
- def union(self, object1, object2):
- '''\
- Combine the sets that contain the two objects given.
- Both objects must be Python hashable.
- If either or both objects are unknown, will make them known, and combine them.'''
- o1p = self.find(object1)
- o2p = self.find(object2)
- if o1p != o2p:
- on1 = self.objects_to_num[o1p]
- on2 = self.objects_to_num[o2p]
- w1 = self.num_weights[on1]
- w2 = self.num_weights[on2]
- if w1 < w2:
- o1p, o2p, on1, on2, w1, w2 = o2p, o1p, on2, on1, w2, w1
- self.num_weights[on1] = w1+w2
- del self.num_weights[on2]
- self.parent_pointers[on2] = on1
- self.unique -= 1
- def getUnique(self):
- return self.unique
- class mod_calc:
- def __init__(self, m):
- self.m = m
- self.fact_table = None
- self.pre_fact(m)
- def pre_fact(self, m):
- f = 1
- res = [1]
- for n in range(1, m):
- f = (f*n)%m
- res.append(f)
- return res
- def factorial(self, n):
- if self.fact_table == None:
- self.fact_table = self.pre_fact(self.m)
- if n==0:
- return 1
- r = n%self.m
- k = n//self.m
- kk = 1
- if k%2==1:
- kk = -1
- return (self.fact_table[r]*self.factorial(k)*kk)%self.m
- def fact_ord(self, n):
- r = n%self.m
- k = n//self.m
- if k==0:
- return 0
- return k+self.fact_ord(k)
- def gcd(self, a, b):
- if b==0:
- return [1,0]
- k = a//b
- r = a-b*k
- g = self.gcd(b, r)
- return [g[1], g[0]-g[1]*k]
- def inv(self, x):
- g = self.gcd(self.m, x)
- return g[1]%self.m
- def ncr(self, n, r):
- if self.fact_ord(n)>self.fact_ord(r)+self.fact_ord(n-r):
- return 0
- return (self.factorial(n)*self.inv((self.factorial(r)*self.factorial(n-r))%self.m))%self.m
- def rotate_coordinates_clockwise(xr, yr, alpha):
- """point stays still, coordinate axis rotate clockwise by angle alpha"""
- y = yr * math.cos(alpha) + xr * math.sin(alpha)
- x = xr * math.cos(alpha) - yr * math.sin(alpha)
- return x, y
- def point_left_line(a, b, c):
- """a and b are two points of line, showing direction. c is point to be determined"""
- r = (b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0])
- if r > 1e-15:
- return True
- elif r < -1e-15:
- return False
- return None
- def convex_hull(points):
- points = sorted(set(points))
- if len(points) <= 1:
- return points
- def cross(o, a, b):
- return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
- lower = []
- for p in points:
- while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
- lower.pop()
- lower.append(p)
- upper = []
- for p in reversed(points):
- while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
- upper.pop()
- upper.append(p)
- return lower[:-1] + upper[:-1]
Add Comment
Please, Sign In to add comment