#!/usr/bin/env python
#
# recursion
#
# prints out the best coins

import copy
def findbest(origarray, denom):
    current = copy.deepcopy(origarray)
    i =1
    while(i < size):
        if(i in denom):
            current[i] = 1
            coinlist[i] = [i]
        else:
            k = 1
            while(k < i):
                c = current[k] + current[i-k]
                if(c < current[i]):
                    current[i] = c
                    coinlist[i] = coinlist[k] + coinlist[i-k]
                k+=1
        # print i, current[i], coinlist[i]
        i+=1
    return sum(current)

size= 100
coinlist = [[]]
origarray= [0] # costs nothing for price of 0
i = 1
while(i < size):
    origarray.append(100)
    coinlist.append([])
    i+= 1
# print origarray

bestval = 10000
bestdenom = []
i = 2
while(i < 60):
    j= i+1
    while(j < 70):
        denom = [1, i, j]
        x = findbest(origarray, denom)
        if(x < bestval):
            bestval = x
            bestdenom = denom
        j+=1
    i+=1





print(findbest(origarray, bestdenom))
print(bestdenom)
