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];
		}
	}
}