CCC 2015 J5 - Pi-Day

1# CCC 2015 Junior 5: Pie Day2#3# This is a recursion problem (or possibliy a Dynamic Programming problem)4#5# This is the recursive solution. 6# 7# Given n (number of pieces of pie) and k (number of people) and the minimum8# number of pieces that can be taken, the number of ways the pie can be destributed9# is:10#     1 if n = k or k = 111#     otherwise it is the sum of the ways of (n-i, k-1, i) where i goes from12#                min to n/k (inclusive)13#14# an example might help: pi(9,4,1)15#   n = 9, k = 4 and min = 116#   for this the answer is calculated as follows:17#       the first person could take 1 piece leaving us the task of finding the ways18#                with now 8 pieces (9-1), 3 people and a min of 1 (= pi(8,3,1))19#       the first person could take 2 pieces leaving us the task of finding the ways20#                with now 7 pieces (9-2), 3 people and a min of 2 (= pi(7,3,2))21#       the first person could NOT take 3 pieces (or more)_because that would leave 622#                pieces for 3 people and since the first person took 3, they23#                would have to take at least 3 themselves and that's 9 not 6 pieces!24#                in general, the most the first person person can take is25#                                               n/k (eg 9/4 = 2)26#27# The recursion as described above works fine, BUT is too slow for the28# later data sets, SO to avoid calculating the same thing twice29# there is a "visited" array. This is a large 3D array keeping track of all30# previous results. Half the running time (and code) is devoted to creating it 31# and initializing it to 0. In the recursion, if the visited array knows the answer,32# use it and don't recurse, otherwise calculate and store the answer in visited. 33#34# the worst case, data set 10, takes about 3 sec on my old35#          XP Pentium 4 CPU, 3.2Ghz, 1G RAM machine, using Python. 36 37visited = []38 39def pi(n,k,min):40    if visited [n][k][min] == 0:       41        if n == k:42            visited[n][k][min] = 143        elif k == 1:44            visited[n][k][min] = 145        else:46            t = 047            for i in range (min, (n / k)+1):48                t = t + pi(n-i, k-1, i)49            visited[n][k][min] = t50    return visited[n][k][min]51 52 53file = open("j5.10.in", "r")54n = int(file.readline())55k = int(file.readline())56 57for i in range(n+1):58    x = []59    for j in range(k+1):60        t = []61        for kk in range(n+1):62            t.append (0)63        x.append(t)64    visited.append(x)65 66print pi(n,k,1)67 68 69