#!/usr/local/bin/python3
# Author: Dr. Robert Heckendorn, Computer Science Department, University of Idaho, 2013
from lib import *

# for coins in positions 0..len(coins)-1
# assume coins in increasing order and coins[0] = 1
# f(i) is the minimum number of coins that adds to i
def change(coins, n) :
#    print(coins)
    f = array(n+1, 0)
    f[0] = 0

    # for up to the amount you want to make change for
    for i in range(1, n+1) :
        tmp = None   # possible number of coins
        j = 0
        # try each type of coin that is legal to use here
        while j<len(coins) and i>=coins[j] :
            if tmp==None or f[i-coins[j]]<tmp :
                tmp = f[i-coins[j]]
            j+=1
        f[i] = tmp + 1
#    print(f)
    return f[len(f)-1]

for n in range(1, 100) :
    print(n, change([1, 2, 10, 20, 100], n))