1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 674 Coin Change
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=615
*
* @author Christoph Hausmann
* @version 0.1, 11/18/2009
*
* Method : Counting Change Problem
* Status : Accepted
* Runtime: 0.940
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class CoinChange_674 {
public static void main(String... args) throws IOException {

final int[] coins = {50,25,10,5,1};

final long[] nway = calc(coins,7489);

final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

while(true) {

final String curLine = br.readLine();

if(curLine == null)
break;


final int n = Integer.parseInt(curLine);

System.out.println(nway[n]);

}
}

public static long[] calc(int[] coins, int n) {
int i,j,v,c;
final long[] nway = new long[7490];

v = 5;
nway[0] = 1;
for (i = 0; i < v; i++) {
c = coins[i];
for (j = c; j <= n; j++)
nway[j] += nway[j-c];
}

return nway;
}
}