top of page

CCC 2015 J5: π-day

Updated: Nov 1, 2020

Use recursive to solve it:

if pieces < people: return 0 if people == 1 or pieces == people: return 1

return piemap[(pieces, people)] =

pie(pieces - 1, people - 1) + pie(pieces - people, people)


n = int(input())
k = int(input())

piemap = dict()


def pie(pieces, people):
    if pieces < people:
        return 0
    if people == 1 or pieces == people:
        return 1
   
    return pie(pieces - 1, people - 1) + pie(pieces - people, people)
   


DP1 solution:

save the above middle result, then do recursive


n = int(input())
k = int(input())
piemap = dict()
def pie(pieces, people):
    if pieces < people:
        return 0
    if people == 1 or pieces == people:
        return 1
    if (pieces, people) in piemap:
        return piemap[(pieces, people)]
    piemap[(pieces, people)] = pie(pieces - 1, people - 1) + pie(pieces - people, people)
    return piemap[(pieces, people)]


print(pie(n, k))

DP2 solution:

way[i][j] = way[i-1][j-1] + way[i-j][j]

pizza = int(input())
people = int(input())
way = [[0 for i in range(people+1)] for i in range(pizza+1)]
way[0][1] = 1
for i in range(1, pizza+1):
    for j in range(1, min(people, i)+1):
        way[i][j] = way[i-1][j-1] + way[i-j][j]
print(way[pizza][people])


print(pie(n, k))

Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,

Comments


bottom of page