2005rb1.c

#include <stdio.h>

int main(void)
{
	int y10,y50,y100,y500;
	int c10,c50,c100,c500;
	int m10,m50,m100,m500;
	int min10,min50,min100,min500;
	int m,i,j,k,l,harau,oturi,mai,min;
	
	while(1){
		scanf("%d", &m);
		if(m==0) break;
		
	 	scanf("%d %d %d %d",&y10, &y50, &y100, &y500);
	 	
		min=20*4; // 最小枚数を調べる。初期値は最大で各硬貨20枚なのでこの 様に設定
		min10=min50=min100=min500=0;
		
		// 全ての場合について調べる
		for(i=0; i<=y10; i++){					// 10円
			for(j=0; j<=y50; j++){				// 50円
				for(k=0; k<=y100; k++){			// 100円
					for(l=0; l<=y500; l++){		// 500円
 						harau=i*10+j*50+k*100+l*500;	 // 払うお金
						oturi=harau-m;				 	// お釣
						if(oturi<0) continue;			 // おつりがマイナスなら次の場合
						
						// おつりの枚数を求める
						c500=oturi/500;
						c100=(oturi%500)/100;
						c50 =(oturi%100)/50;
						c10 =(oturi%50)/10;	
						
						// 支払後の手持の枚数を求める
						m10=y10-i+c10;
						m50=y50-j+c50;
						m100=y100-k+c100;
						m500=y500-l+c500;
						mai=m10+m50+m100+m500;
						
						// 最小の場合更新
						if(min>mai){
							min=mai;
							min10=i;
							min50=j;
							min100=k;
							min500=l;
						}
					}
				}
			}
		}
		if(min10>0){
			printf("10 %d\n", min10);
		}
		if(min50>0){
			printf("50 %d\n", min50);
		}
		if(min100>0){
			printf("100 %d\n", min100);
		}
		if(min500>0){
			printf("500 %d\n", min500);
		}
		printf("\n");
	}
	
	return 0;
}