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.


 
["Count the coins" problem for Rosetta Code.]
[EDSAC program, Initial Orders 2.]
 
            T51K  P56F [G parameter: print subroutine]
            T54K  P94F [C parameter: coins subroutine]
            T47K P200F [M parameter: main routine]
 
[========================== M parameter ===============================]
            E25K TM GK 
[Parameter block for US coins. For convenience, all numbers
 are in the address field, e.g. 25 cents is P25F not P12D.]
      [0]   UF SF   [2-letter ID]
            P100F   [amount to be made with coins]
            P4F     [number of coin values]
            P1F P5F P10F P25F [list of coin values]
      [8]   P@      [address of US parameter block]
[Parameter block for UK coins]
      [9]   UF KF
            P100F
            P7F
            P1F P2F P5F P10F P20F P50F P100F
     [20]   P9@     [address of UK parameter block]
[Enter with acc = 0]
     [21]   A8@     [load address of parameter block for US coins]
            T4F     [pass to subroutine in 4F]
     [23]   A23@    [call subroutine to calculate and print result]
            G13C
            A20@    [same for UK coins]
            T4F
     [27]   A27@
            G13C
            ZF      [halt program]
 
[========================== C parameter ===============================]
[Subroutine to calculate and print the result for the given amount and
 set of coins. Address of parameter block (see above) is passed in 4F.]
 
            E25K TC GK
      [0]   SF      [S order for start of coin list]
      [1]   A1023F  [start table at top of memory and work downwarda]
      [2]   PF      [S order for exclusive end of coin list]
      [3]   P2F     [to increment address by 2]
      [4]   OF      [(1) add to address to make O order
                     (2) add to A order to make T order with same address]
      [5]   SF      [add to address to make S order]
      [6]   K4095F  [add to S order to make A order, dec address]
      [7]   K2048F  [set teleprinter to letters]
      [8]   #F      [set teleprinter to figures]
      [9]   !F      [space character]
     [10]   @F      [carriage return]
     [11]   &F      [line feed]
     [12]   K4096F  [teleprinter null]
[Subroutine entry. In this EDSAC program, the table used
 in the algorithm grows downward from the top of memory.]
     [13]   A3F     [plant jump back to caller, as usual]
            T89@
            A4F     [load address of parameter block]
            A3@     [skip 2-letter ID]
            A5@     [make S order for amount]
            U27@    [plant in code]
            A3@     [make S order for first coin value]
            U@      [store it]
            A6@     [make A order for number of coins]
            T38@    [plant in code]
            A2F     [load 1 (in address field)]
     [24]   T1023F  [store at start of table]
[Set all other table entries to 0]
            A24@
            T32@
     [27]   SF      [acc := -amount]
     [28]   TF      [set negative count in 0F]
            A32@    [decrement address in manufactured order]
            S2F
            T32@
     [32]   TF      [manufactured: set table entry to 0]
            AF      [update negative count]
            A2F
            G28@    [loop until count = 0]
[Here acc = 0. Manufactured order (4 lines up) is T order
 for inclusive end of table; this is used again below.]
            A@      [load S order for first coin value]
            U43@    [plant in code]
     [38]   AF      [make S order for exclusive end of coin list]
            T2@     [store for comparison]
[Start of outer loop, round coin values]
     [40]   TF      [clear acc]
            A1@     [load A order for start of table]
            U48@    [plant in code]
     [43]   SF      [manufactured order: subtract coin value]
[Start of inner loop, round table entries]
     [44]   U47@    [plant A order in code]
            A4@     [make T order for same address]
            T49@    [plant in code]
[The next 3 orders are manufactured at run time]
     [47]   AF      [load table entry]
     [48]   AF      [add earlier table entry]
     [49]   TF      [update table entry]
            A32@    [load T order for inclusive end of table]
            S49@    [reached end of table?]
            E60@    [if yes, jump out of inner loop]
            TF      [clear acc]
            A48@    [update the 3 manufactured instructions]
            S2F
            T48@
            A47@
            S2F
            G44@    [always loops back, since A < 0]
[End of inner loop]
     [60]   TF      [clear acc]
            A43@    [update S order for coin value]
            A2F
            U43@
            S2@     [reached exclusive end?]
            G40@    [if no, loop back]
[End of outer loop]
[Here with acc = 0 and result at end of table]
[Value is in address field, so shift 1 right for printing]
            A32@    [load T order for end of tab;e]
            S4@     [make A order for same address]
            T79@    [plant in code]
            A4F     [load address of parameter block]
            A4@     [make O order for 1st char of ID]
            U75@    [plant in code]
            A2F     [same for 2nd char]
            T76@
            O7@     [set teleprinter to letters]
     [75]   OF      [print ID, followed by space]
     [76]   OF O9@
            O8@     [set teleprinter to figures]
     [79]   AF      [maunfactured order to load result]
            RD      [shift 1 right for printing]
            TF      [pass to print routine]
            A9@     [replace leading 0's with space]
            T1F
     [84]   A84@    [call print routine]
            GG
            O10@ O11@  [print CR, LF]
            O12@    [print null to flush teleprinter buffer]
     [89]   ZF      [replaced by jump back to caller]
 
[============================= G parameter ===============================]
            E25K TG GK 
[Subroutine to print non-negative 17-bit integer. Always prints 5 chars.
 Caller specifies character for leading 0 (typically 0, space or null).
 Parameters: 0F = integer to be printed (not preserved)
             1F = character for leading zero (preserved)
 Workspace: 4F..7F, 38 locations]
            A3FT34@A1FT7FS35@T6FT4#FAFT4FH36@V4FRDA4#FR1024FH37@E23@O7FA2F
            T6FT5FV4#FYFL8FT4#FA5FL1024FUFA6FG16@OFTFT7FA6FG17@ZFP4FZ219DTF
 
[========================== M parameter again ===============================]
            E25K TM GK
            E21Z    [define entry point]
            PF      [enter with acc = 0]
 