Problem B
Pay the Price
Input: standard input
Output: standard output
Time Limit: 2 seconds
Memory Limit: 32 MB
In
ancient days there was a country whose people had very interesting habits. Some
of them were lazy, some were very rich, some were very poor and some were
miser. Obviously, some of the rich were miser (A poor was never miser as he had
little to spend) and lazy but the poor were lazy as well (As the poor were lazy
they remained poor forever). The following things were true for that country
a)
As the rich were miser, no things price was more than 300 dollars (Yes! their currency was
dollar).
b)
As all people were lazy, the price of everything was integer
(There were no cents and so beggars always earned at least one dollar)
c)
The values of the coins were from 1 to 300 dollars, so
that the rich (who were idle) could pay any price with a single coin.
Your
job is to find out in how many ways one could pay a certain price using a limited
number of coins (Note that the number of coins paid is limited but not the
value or source. I mean there was infinite number of coins of all values). For
example, by using three coins one can pay six dollars in 3 ways, 1+1+4, 1+2+3, and 2+2+2. Similarly, one can pay 6 dollars using 6 coins
or less in 11 ways.
Input
The
input file contains several lines of input. Each line of input may contain 1, 2
or 3 integers. The first integer is
always N (0<=N<=300), the
dollar amount to be paid. All other integers are less than 1001 and non-negative.
Output
For
each line of input you should output a single integer.
When
there is only one integer N as
input, you should output in how many ways N
dollars can be paid.
When
there are two integers N and L1 as input, then you should output in
how many ways N dollars can be paid
using L1 or less coins.
When
there are three integers N, L1 and L2 as input, then you should output in how many ways N dollars can be paid using L1, L1+1 …, L2 coins (summing
all together). Remember that L1 is not
greater than L2.
Sample Input
6
6 3
6 2 5
6 1 6
Sample Output
11
7
9
11
(The Decider Contest, Problem setter: Shahriar Manzoor)