AOJ_2007

硬貨の枚数を少なくしたい。
所持金をすべて払ったときのおつりを求め、そこから重複して払った硬貨の枚数を
引いていけばいい。たぶん一瞬で解が求まるから、８秒の時間制限も余裕。

#include <cstdio>
#include <algorithm>
using namespace std;

int p; //代金
int coin[4]; //各硬貨の枚数
const int coin_g[4] = {10, 50, 100, 500};

int main(){
	bool f = false;
	while(scanf("%d", &p)){
		if(p == 0) return 0;
		if(f) printf("\n");
		int sum = 0; //所持金の合計
		for(int i = 0; i < 4; i++){
			scanf("%d", &coin[i]);
			sum += coin[i] * coin_g[i];
		}
		int change = sum - p;
		for(int i = 3; i >= 0; i--){
			int t = change / coin_g[i]; //おつりに含まれるcoin_g[i]円硬貨の枚数
			coin[i] -= t; //重複している分を引く
			change -= coin_g[i] * t;
		}
		for(int i = 0; i < 4; i++){
			if(coin[i] > 0)
				printf("%d %d\n", coin_g[i], coin[i]);
		}
		f = true;
	}
	return 0;
}