1.


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

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 674 Coin Change
* Link: http://uva.onlinejudge.org/external/6/674.pdf
*
* @author Rolf Schirm
* @version 1.0, 04/06/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.108
*/
public class Main {
public static void main(String... args) throws Exception {
final BufferedReader scan = new BufferedReader(new
InputStreamReader(System.in));

final int length = 7489/5 + 1;

/**
* Anzahl der Kombinationen bei denen mindestens einmal die
* Münze 10 vorkommt und zugleich 10 die höchste Münze ist.
*/
final long[] f10 = new long[length];

/**
* Anzahl der Kombinationen bei denen mindestens einmal die
* Münze 25 vorkommt und zugleich 25 die höchste Münze ist.
*/
final long[] f25 = new long[length];

/**
* Anzahl der Kombinationen bei denen mindestens einmal die
* Münze 50 vorkommt und zugleich 50 die höchste Münze ist.
*/
final long[] f50 = new long[length];

/**
* Anzahl der Gesamten Kombinationen aus 1, 5, 10, 25 und 50
* ist die Summe aus f1 (= 1), f5 (= i), f10, f25 und f50.
*/
final long[] fsum = new long[length];

for(int i = 2; i < length; i++) {
f10[i] = i - 1 + f10[i-2];
}

for(int i = 5; i < length; i++) {
f25[i] = i - 4 + f10[i-5] + f25[i-5];
}

for(int i = 10; i < length; i++) {
f50[i] = i - 9 + f10[i-10] + f25[i-10] + f50[i-10];
}

for(int i = 0; i < length; i++) {
fsum[i] = 1 + i + f10[i] + f25[i] + f50[i];
}

String line;

while((line = scan.readLine()) != null) {
System.out.println(fsum[Integer.parseInt(line)/5]);
}
}
}

2.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 674 - Coin Change
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=615
* @author Mitterreiter Christian
* @author Posselt Christian
* @version 1.0, 04/05/2011
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.164
*/


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;
wechsel[0]=1;

//Vorberechnung:
for(int i=0; i<muenzen.length; 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();
}
}
}




----------------------------------------
1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 674 - Coin Change
* Link: http://uva.onlinejudge.org/external/6/674.pdf
*
* @author Philippe Brousse
* @version 1.0, 10/27/2010
*
* Method : Counting Change
* Status : Accepted
* Runtime: 1.764
*/
package coinchange;

import java.util.Scanner;

/**
*
* @author Philippe Brousse
*/
public class Main
{

/**
* @param Kommandozeilenargumente
*/
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
// Münzwerte
final int[] coins = new int[]
{
50, 25, 10, 5, 1
};
// Anzahl möglicher Münzkombinationen für bis zu 7489 cents
long[] ways = new long[7490];
// 0 cent auf 1 art wechselbar
ways[0] = 1;
// Möglichkeiten berechnen
for (int coin : coins)
{
for (int j = coin; j <= 7489; j++)
{
ways[j] += ways[j - coin];
}
}
// Möglichkeit auslesen
while (input.hasNext())
{

int amount = input.nextInt();
System.out.println(ways[amount]);

}
input.close();
}
}



2.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 674 - Coin Change
* Link: http://uva.onlinejudge.org/external/6/674.html
*
* @author Barny Porcio
* @version 1.0, 05/09/2010
*
* Method : -
* Status : Accepted
* Runtime: 0.096
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class CoinChange674 {

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] coin = {50,25,10,5,1};
int[] ans = new int[7490];
ans[0] = 1;
for (int i = 0; i < coin.length; ++i) {
for (int j = coin[i]; j < ans.length; j++){
ans[j] += ans[j-coin[i]];
}
}
while(br.ready()){
System.out.println(ans[Integer.parseInt(br.readLine())]);
}
}
}

2.

/** * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* * Problem: 674 - Coin Change
* * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=615
* * Savkina Ekaterina
* * @version 1.0, 06/17/2010
* *Method : Ad-Hoc
* * Status : Accepted
* * Runtime: 0.932 */
package coins_change;

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

public class Main {

public static int[] coins = { 50, 25, 10, 5, 1 };
static int MAX = 7489;

public static void main(String... args) throws NumberFormatException,
IOException {
BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
int v = 5;
int[] mway = new int[MAX + 1];
mway[0] = 1;
for (int i = 0; i < v; i++) {
int c = coins[i];
for (int j = c; j <= MAX; j++)
mway[j] += mway[j - c];
}
while (sc.ready()) {
int money = Integer.parseInt(sc.readLine());
// if (money == 0)
//break;


System.out.print(mway[money] + "\n");

}
}
}


2.

package acm_674_coin_change;

import java.util.Scanner;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_674_coin_change
* Link:
*
* @author Martin Lambeck
* @version 1.0, 01.09.2010
*
* Method : dp
* Status : Accepted
* Runtime: 2.660
*/


public class Main
{
static Scanner sc = new Scanner(System.in);

final static int MAX = 7500;

static long[] w = new long[MAX+1];

public static void main(String... args)
{
w[0] = 1;

dp(1);
dp(5);
dp(10);
dp(25);
dp(50);


while (testcase())
;
}

public static boolean testcase()
{
if (!sc.hasNextInt())
return false;

int price = sc.nextInt();

System.out.printf("%d%n", w[price]);

return true;
}

static void dp(int c)
{
for (int i = 0; i <= MAX; i++)
{
if (i+c > MAX)
return;

w[i+c] += w[i];
}
}
}