1. JAVA, Simon Baumgartner


import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/*
* ACM Programming Contest
* Problem: 674 Coin Change
* Status: Accepted
* Runtime: 0.888
* Date: 2009-05-28
* Author: Simon Baumgartner
*
*/

public class Main {

public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader in = new BufferedReader(new FileReader("input.txt"));
int[] coins = new int[]{1, 5, 10, 25, 50};
int maxNr = 7499;
int[][] table = new int[coins.length][maxNr];

for(int y = 0; y < maxNr; y++)
{
for(int x = 0; x < coins.length; x++)
{
if(x == 0 || y == 0)
table[x][y] = 1;
else{
int index = y - coins[x];
int nr2 = (index >= 0 ? table[x][index] : 0);
table[x][y] = table[x-1][y] + nr2;
}
}
}

String line;
while((line = in.readLine()) != null){
int nr = Integer.parseInt(line);
System.out.println(table[4][nr]);
}
}

}