spoj#TPC07. Change
Change
How many ways are there to pay n cents? We assume that the payment must be made with pennies (1 cent), nickels (5 cents), dimes (10 cents), quarters (25 cents), and half-dollars (50 cents).
For example, there are four ways to pay 13 cents, namely (13 pennies), (2 nickels, 3 pennies), (1 nickel, 8 pennies), and (1 dime, 3 pennies).
Input
The input will contain multiple test cases. Each test case contains a single line with a single integer n (1 ≤ n ≤ 1000000000).
The input will be terminated by the end of file.
Output
For each input integer n, output how many ways are there to pay n cents in a single line.
Sample Input
13 100000000
Sample Output
4 66666793333412666685000001