1.

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

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 357 Let Me Count The Ways
* Link: http://uva.onlinejudge.org/external/3/357.pdf
*
* @author Rolf Schirm
* @version 1.0, 03/25/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.556
*/
public class Main {
public static void main(String... args) throws Exception {
final BufferedReader scan = new BufferedReader(new
InputStreamReader(System.in));

final int length = 30000/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) {
final int number = Integer.parseInt(line);
final long result = fsum[number/5];

if(result == 1) {
System.out.println("There is only 1 way to produce " + number + "
cents change.");
} else {
System.out.println("There are " + result + " ways to produce " +
number + " cents change.");
}
}
}
}

2.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 357 - Let me count the ways
* Link: http://uva.onlinejudge.org/external/3/357.pdf
*
* @author Christian Posselt
* @author Christian Mitterreiter
* @version 1.0, 06.04.2011
*
* Status: Accepted
* Time: 0.764
*/

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

public class Main
{


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

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

//possible amounts to change with
int[] coin = new int[]{1,5,10,25,50};

//precalculate all changes up to 30000 cents worth of input
//BigInteger needed because of range
BigInteger[] possibilities = new BigInteger[30001];
possibilities[0] = BigInteger.ONE;

for(int i=0;i<coin.length;i++)
{
int c = coin[i];
for(int j=c;j<=30000;j++)
{
if(possibilities[j] == null)
possibilities[j] = BigInteger.ZERO;
possibilities[j] = possibilities[j].add(possibilities[j-c]);
}

}

do
{

int amount = Integer.parseInt(reader.readLine());

//if amount < 5, there is only one way of calculation
if(amount>=4)
System.out.println("There are " + possibilities[amount] + " ways to produce " + amount + " cents change.");
else
System.out.println("There is only 1 way to produce " + amount + " cents change.");

}
while(reader.ready());

}



}

3.

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

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 357 Let Me Count The Ways
* Link: http://uva.onlinejudge.org/external/3/357.pdf
*
* @author Weigl Joseph
* @author Müller Thomas
* @version 1.0, 04/13/2011
*
* Status : Accepted
* Runtime: 1.632
*/

public class Main {

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

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int input;
int maxInput = 30000;
BigInteger[] ways = new BigInteger[maxInput + 1];
int[] coins = {50, 25, 10, 5, 1};
ways[0] = BigInteger.valueOf(1);

for(int i : coins){
for(int j = i; j <= maxInput; j++){
if(ways[j] == null)
ways[j] = BigInteger.ZERO;
if(ways[j-i] == null)
ways[j-i] = BigInteger.ZERO;
ways[j]= ways[j].add(ways[j-i]);
}
}

while(reader.ready()){
input = Integer.parseInt(reader.readLine());
if(ways[input] != BigInteger.ONE)
System.out.printf("There are %d ways to produce %d cents change.%n", ways[input], input);
else
System.out.printf("There is only 1 way to produce %d cents change.%n", input);

}

}

}


--------------
1.
package acm_357_let_me_count_the_ways;

import java.util.Scanner;

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


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

final static int MAX = 30000;

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();

if (w[price] == 1)
System.out.printf("There is only 1 way to produce %d cents change.%n", price);
else
System.out.printf("There are %d ways to produce %d cents change.%n", w[price], 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];
}
}
}