USACO Cow Pedigrees, Dynamic Programming (Python)

USACO Cow Pedigrees¶

In [1]:

# SAMPLE INPUT
#
# 5 3

In [2]:

fin = open ('nocows.in', 'r')
fout = open ('nocows.out', 'w')
N,K  = map(int, fin.readline().split())
N=9
K=4
print(N,K)

9 4

In [3]:

# columns are number of cows
# rows are number of levels
# entries are number of ways to configure n cows with that many levels OR LESS.

dp = [[0 for col in range(N+1)] for row in range(K+1)]
for row in range(1,K+1):
    dp[row][1]=1
    if row>1:
        dp[row][3]=1
        
for row in dp:
    print(row)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0]

In [4]:

for j in range(5,N+1,2):
    for i in range(3,K+1):
        sum = 0
        print(i,j)
        for m in range(1,j,2):
            # dp(i,j)=sum(dp(i-1,m) * dp(i-1,j-m-1)) as m goes from 0 to j-1
            sum+=dp[i-1][m]*dp[i-1][j-m-1]
        dp[i][j]=sum  

3 5
4 5
3 7
4 7
3 9
4 9

In [5]:

for row in dp:
    print(row)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 2, 0, 1, 0, 0]
[0, 1, 0, 1, 0, 2, 0, 5, 0, 6]

In [6]:

ans = dp[K][N]-dp[K-1][N]
print("ANSWER",ans,ans%9901)
fout.write(str(ans%9901)+"\n")
fout.close()

ANSWER 6 6