1. 


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem: Coin Change (674)
* @author Christian Mitterreiter
* @author Rolf Luigs
* @version 1.0, 06/15/2009
* Status : Accepted
* Runtime: 0.972
*/


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

public class Main {

public static void main(String[] args) throws IOException {

//Initialisierung
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer s = null;
String in = null;
final int MAX = 7490;
long[] wechsel = new long[MAX+1]; //Array für Anzahl der Wechselmöglichkeiten
int[] muenzen = new int[] {50,25,10,5,1}; //mögliche Münzen
int current = 0;
int v = 5; //Anzahl der möglichen Münzen
wechsel[0]=1;

//Vorberechnung:
for(int i=0; i<v; i++) { //durchläuft die einzelnen Münzentypen
current = muenzen[i];
wechsel[current]++;
for(int j = current+1; j<=MAX; j++) {
wechsel[j] += wechsel[j-current]; //Anzahl der Wechselmöglichkeiten berechnen
}
}

in = br.readLine();

while(in!=null) { //Ausgabe der Wechselmöglichkeiten der eingelesenen Beträge
s = new StringTokenizer(in);
while(s.hasMoreElements()) {
System.out.println(wechsel[Integer.parseInt(s.nextToken())]);
}
in = br.readLine();
}
}
}

2.


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem: Coin Change (674)
* @author Christian Mitterreiter
* @author Rolf Luigs
* @version 1.0, 06/15/2009
* Status :
* ALTERNATIV-LÖSUNG MIT THREADS: Werte werden zur selben Zeit vorberechnet, wie die
* Eingabewerte eingelsen werden. Nach dem Ende des Einlesens,
* (EOF) beginnt die Ausgabe.
*/


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main2 {

public static void main(String[] args) {

final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
final int MAX = 7490;
final long[] wechsel = new long[MAX+1];
final int[] muenzen = new int[] {50,25,10,5,1};
final int v = 5;
wechsel[0]=1;
final ArrayList<Boolean> m = new ArrayList<Boolean>();
final ArrayList<Integer> input = new ArrayList<Integer>();
m.add(false);
m.add(false);

new Thread() { //Werte berechnen
public void run() {
for(int i=0; i<v; i++) {
int current = muenzen[i];
wechsel[current]++;
for(int j= current+1; j<=MAX; j++) {
wechsel[j] += wechsel[j-current];
}
}
synchronized(m) {
m.set(0, true);
m.notifyAll();
}
}
}.start();

new Thread() { //Eingabe abspeichern
public void run() {
String in = null;
StringTokenizer s = null;

while(true) {
try {
in = br.readLine();
}
catch (IOException e) {}
if(in == null) break;
s = new StringTokenizer(in);
while(s.hasMoreElements()) {
input.add(Integer.parseInt(s.nextToken()));
}
}
synchronized(m) {
m.set(1, true);
m.notifyAll();
}
}
}.start();


synchronized(m) { //wartet auf die anderen beiden Threads
while(m.contains(false)) {
try {
m.wait();
} catch (InterruptedException e) {}
}
}

while(!input.isEmpty()) { //Ausgabe
System.out.println(wechsel[input.remove(0)]);
}
}
}



3.

/* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #674 (Coin Change)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=615
*
* @author Dennis Wilfert
* @author Johann Studt
* @version 1.0, 07/02/2009
*
* Status : Accepted
* Runtime: 0.240
*/
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
int[] nway = new int[7490];
// 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 7489 cent berechnen
for(i=0; i<coin.length; i++){
c = coin[i];
for(j = c; j<=7489; j++)
nway[j] += nway[j-c];
}
while(true){

string = reader.readLine();

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

output.append(nway[amount]);
output.append("\n");
}
p.print(output);
p.flush();
}

}