```On Tue, Jul 31, 2001 at 02:14:41PM +0900, teespy wrote:
> Sorry for the late response, but I was playing with this a bit and I finished my ultra-slow solution. Anyways, i learned some things from it, so here it is if someone is still intrested.

It's always good to learn stuff :)

> I?m pretty sure there are better algorithms to do it, I?d like to take a look if you want  to show them.

Well it's not much but here is my attempt. I gave up on it since it didn't seem
like anyone was interested in pursuing it any further. It can calculate the
number of possiblities for \$100 in 1 hour 23 min. That's without initializing
the table. With the table it can do it in 0.03 secs.

And here it is

class Counter
def initialize
denoms = [10000, 5000, 2000, 1000, 500, 200, 100, 50, 25, 10,
5, 1]
amounts = [9823546661906, 58853234019, 155848898, 3237135,
111023, 2729, 293, 50, 13, 4, 2, 1]

@table = {}
@denoms = {}

index = 0
denoms.each do |i|
@denoms[i] = denoms[index..-1]
@table[i] = {}
@table[i][i] = amounts[index]
index = index + 1
end
end

def count( amt, num_of_denoms = 10000 )
if @table.has_key? amt
if @table[amt].has_key? num_of_denoms
return @table[amt][num_of_denoms]
end
end

ways = 0

@denoms[num_of_denoms].each do |i|
if i > amt
next
elsif amt - i == 0
ways = 1
else
ways += count( amt - i, i )
end
end
@table[amt] = {}
@table[amt][num_of_denoms] = ways
end
end

counter = Counter.new
print counter.count( \$*[0].to_i ), "\n"
```