1. 


/* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #357 (Let Me Count The Ways)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=293
*
* @author Dennis Wilfert
* @author Johann Studt
* @version 1.0, 07/02/2009
*
* Status : Accepted
* Runtime: 0.228
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;


public class Main {

public static void main(String[] args) throws IOException {
StringBuilder output = new StringBuilder();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter p = new PrintWriter(new BufferedOutputStream(System.out));
int[] coin = new int[]{50, 25, 10, 5, 1};
// Betrag als Integerwert in cent
int amount;
// Kombinationsmöglichkeiten für die verschiedenen Beträge
long[] nway = new long[30001];
// Zahl als String
String string;
// Hilfsvariablen
int c, i, j;
nway[0] = 1;
// Sämtliche Kombinationen für alle Beträge von 0 cent bis 30000 cent berechnen
for(i=0; i<coin.length; i++){
c = coin[i];
for(j = c; j<=30000; j++)
nway[j] += nway[j-c];
}
while(true){

string = reader.readLine();

if(string == null)break;
// Betrag als int-Wert
amount = Integer.parseInt(string);

if(nway[amount]==1){
output.append("There is only 1 way to produce ");
output.append(amount);
output.append(" cents change.\n");
}
else{
output.append("There are ");
output.append(nway[amount]);
output.append(" ways to produce ");
output.append(amount);
output.append(" cents change.\n");
}
}
p.print(output);
p.flush();
}

}