IPSC Problem A: Advice for Olivia

http://ipsc.ksp.sk/

ユーロとセントが与えられた時に一番使う貨幣の枚数が少なくなるようにせよ という感じの問題。

配列に使う貨幣を挿入してユーロとセントでそれぞれ大きい方から使っていって使った枚数をそれぞれint[] ansに記録。貪欲法ですね

import java.util.Scanner;

public class IPSC2013_A{
	private static final Scanner sc=new Scanner(System.in);

	public static void main(String[] args){
		int[] coins={1,2,5,10,20,50,1,2,5,10,20,50,100};

		int n=sc.nextInt();
		for(int nn=0;nn<n;nn++){
			int e=sc.nextInt();
			int c=sc.nextInt();
			int[] ans=new int[13];

			for(int i=12;i>=6;i--){
				if(coins[i] <= e){
					e-=coins[i];
					ans[i]++;
					i++;
				}
			}
			for(int i=5;i>=0;i--){
				if(coins[i] <= c){
					c-=coins[i];
					ans[i]++;
					i++;
				}
			}
			System.out.print(ans[0]);
			for(int i=1;i<13;i++){
				System.out.print(" "+ans[i]);
			}
			System.out.println();
		}
	}
}