TPC07 - Change

no tags 

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

hide comments
smso: 2019-05-17 09:33:00

Problem was ripped from "Concrete mathematics" ch.7.
Bottom up dp or recurrence will end in TLE.
Use formula instead.

darryl: 2015-12-30 08:21:01

Learn something new today...

[Lakshman]: 2014-05-19 19:13:22

AC!!!!

Last edit: 2014-05-20 11:16:12
Apoorv Jindal: 2014-02-10 03:38:47

AWESOME problem!

Last edit: 2013-12-24 08:29:31

Added by:abdelkarim
Date:2013-09-28
Time limit:2.929s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:TJU Programming Contest 2007