#!/usr/bin/env python
#
# recursion
#
# prints out the best coins
def findbest(origarray, denom):
 current = 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 current
 
# prints out the best coins
def evaldenom(denom):
  size= 100
  origarray= [0] # costs nothing for price of 0
  i = 1
  while(i < size):
	origarray.append(100)
	i+= 1

  current = origarray
  i =1
  while(i < size):
	if(i in denom):
		current[i] = 1
	else:
		k = 1
		while(k < i):
			c = current[k] + current[i-k]
			if(c < current[i]):
				current[i] = c
			k+=1
	i+=1
  return sum(current)
 

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




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

findbest(origarray, bestdenom)
