import sys
from sets import Set

if len(sys.argv) != 2:
  print "Pass cents postage required"
  sys.exit(1)

# Denominations of stamps available (in cents).
STAMPS = [37, 1, 83, 5, 33, 60, 100]
STAMPS.sort()
STAMPS.reverse()

centsNeeded = int(sys.argv[1])

#--------------------------------------------------
# This taken from http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465
def xuniqueCombinations(items, n):
  if n==0: yield []
  else:
    for i in xrange(len(items)):
      for cc in xuniqueCombinations(items[i+1:],n-1):
        yield [items[i]]+cc

#--------------------------------------------------
# Based on stamps available, find best combo to equal cents.
# Return (total num stamps needed, ((denomination, num stamps of that denomination), ...)).
def calculateStampCombo(cents, stampsAvailable):
  numStampsNeeded = 0
  # A dict is nicer, but use tuple so we can make a Set later
  # (has to be hashable).
  stampsNeeded = []
  for stamp in stampsAvailable:
    numStamps = cents/stamp
    if numStamps > 0:
      stampsNeeded.append((stamp, numStamps))
      numStampsNeeded += numStamps
      cents -= stamp * numStamps
      if cents == 0:
        break

  # Not a valid solution.
  if cents != 0:
    return None, None

  return numStampsNeeded, tuple(stampsNeeded)

#--------------------------------------------------
# Helper function for sort.
def compareStampComboResults(first, second):
  return cmp(first[0], second[0])

#--------------------------------------------------
def printSolution(s):
  output = []
  output.append('%d stamps needed:' % s[0])
  d = dict(s[1])
  stampsNeededKeys = d.keys()
  stampsNeededKeys.sort()
  stampsNeededKeys.reverse()
  for stamp in stampsNeededKeys:
    output.append('%.2f : %d' % (stamp/100., d[stamp]))
  return '\n'.join(output)


#------------------------
# main

# Get all possible combos of the stamps we have.
allStampCombos = [STAMPS]
for n in range(2, len(STAMPS)):
  for x in xuniqueCombinations(STAMPS, n):
    allStampCombos.append(x)

# Find all valid solutions for all possible combos.
solutions = []
for combo in allStampCombos:
  (num, stamps) = calculateStampCombo(centsNeeded, combo)
  if num:
    solutions.append((num, stamps))

# Get the best solutions.
highestDenominationSolution = solutions[0]

# Eliminate dupes and sort by num stamps required.
solutions = list(Set(solutions))
solutions.sort(compareStampComboResults)

output = []
same = ''
output.append("Using fewest stamps%s:")
leastNumberOfStamps = solutions[0][0]
for s in solutions:
  if s[0] == leastNumberOfStamps:
    if highestDenominationSolution == s:
      same = ' (and highest denomination)'
    output.append(printSolution(s))
    output.append('')

if not same:
  output.append('')
  output.append("Using highest denomination:")
  output.append(printSolution(highestDenominationSolution))

print '\n'.join(output) % same