#!/usr/bin/ruby
# Calculate the number of ways to make change for a given amount. Pass
# the amount as number of cents as the only parameter.
 
AMOUNT = Integer(ARGV[0])
 
COINS = [10000, 5000, 1000, 500, 200, 100, 50, 25, 10, 5, 1]
 
# Count the number of ways to make change, given the amount and types of
# coins. The coins are passed as an array sorted from largest to smallest
def ways(amount, coins)
  # When there is only one type of coin, the only way to make change is to 
  # divide the amount evenly by the value of the coin.
  if coins.length == 1
    if amount % coins.first == 0
      1
    else
      0
    end
  else
    # With each possible number of the largest coin, calculate the number
    # of ways to make change with the second largest through smallest coins
    # for the remaining amount recursively, and sum them
    0.step(amount, coins.first).inject(0) do |total_ways, used_amount|
      total_ways + ways(amount - used_amount, coins[1..-1])
    end
  end
end
 
puts ways(AMOUNT, COINS)