There are four types of common coins in   US   currency:

   quarters   (25 cents)
   dimes   (10 cents)
   nickels   (5 cents),   and 
   pennies   (1 cent) 


There are six ways to make change for 15 cents:

   A dime and a nickel 
   A dime and 5 pennies
   3 nickels
   2 nickels and 5 pennies
   A nickel and 10 pennies
   15 pennies


Task

How many ways are there to make change for a dollar using these common coins?     (1 dollar = 100 cents).



Optional

Less common are dollar coins (100 cents);   and very rare are half dollars (50 cents).   With the addition of these two coins, how many ways are there to make change for $1000?

(Note:   the answer is larger than   232).



References

 an algorithm from the book Structure and Interpretation of Computer Programs.
 an article in the algorithmist.
 Change-making problem on Wikipedia.


with Ada.Text_IO;
 
procedure Count_The_Coins is
 
   type Counter_Type is range 0 .. 2**63-1; -- works with gnat
   type Coin_List is array(Positive range <>) of Positive;
 
   function Count(Goal: Natural; Coins: Coin_List) return Counter_Type is
      Cnt: array(0 .. Goal) of Counter_Type := (0 => 1, others => 0);
      -- 0 => we already know one way to choose (no) coins that sum up to zero
      -- 1 .. Goal => we do not (yet) other ways to choose coins
   begin
      for C in Coins'Range loop
         for Amount in 1 .. Cnt'Last loop
            if Coins(C) <= Amount then
               Cnt(Amount) := Cnt(Amount) + Cnt(Amount-Coins(C));
               -- Amount-Coins(C) plus Coins(C) sums up to Amount;
            end if;
         end loop;
      end loop;
      return Cnt(Goal);
   end Count;
 
   procedure Print(C: Counter_Type) is
   begin
      Ada.Text_IO.Put_Line(Counter_Type'Image(C));
   end Print;
 
begin
   Print(Count(   1_00,          (25, 10, 5, 1)));
   Print(Count(1000_00, (100, 50, 25, 10, 5, 1)));
end Count_The_Coins;