package problem_2;
//ComputeChange.java
import java.io.*;

public class ComputeChange {
	public static void main(String[] args){
		try{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			System.out.print("Total amount of money = ");
			Double sum = Double.valueOf(br.readLine());		//讀入總錢數
			solve(sum.doubleValue());		//分錢
		}
		catch(IOException e){
			System.out.println(e);
		}
	}
	
	//分錢，傳入參數sum為總錢數，打印所有可能分法
	public static void solve(double sum){
		int remain = (int)(sum * 100);		//記錄剩余cent量
		int solutionNum = 0;		//記錄分法總數
		System.out.println("Solutions: ");
		for(int i = remain / 100; i >= 0 ; i--){	//按1 dollar進行拆分
			remain -= i * 100;
			for(int j = remain / 25; j>=0; j--){	//按25 cent進行拆分
				remain -= j * 25;
				for(int k = remain / 10; k >= 0; k--){	//按10 cent進行拆分
					remain -= k * 10;
					for(int l = remain / 5; l >= 0; l--){	//按5 cent進行拆分
						remain -= l * 5;
						solutionNum++;
						//輸出分法編號及具體分法
						System.out.println("Solution " + solutionNum + ": ");
						System.out.println("Number of $1.00: " + i);
						System.out.println("Number of $0.25: " + j);
						System.out.println("Number of $0.10: " + k);
						System.out.println("Number of $0.05: " + l);
						System.out.println("Number of $0.01: " + remain);
						System.out.println();
						remain += l * 5;
					}
					remain += k * 10;
				}
				remain += j * 25;
			}
			remain += i * 100;
		}
	}
}