2581.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2581  User Id:fzk 
Memory:36K  Time:0MS
Language:C++  Result:Accepted

Source 

#include"stdio.h"

int main()
{
	int a,b,c,d,e,i,j,k,total,s,value;
	int as,bs,cs,ds;
	double t;

	while( scanf( "%lf %d %d %d %d", &t, &b, &c, &d, &e ) == 5 )
	{
		a = int(t*100);
		total = 99999;
		s = 0; value = 0;

		for( i=0; i<=b && i<total && value+i*25<=a; i++ )
		{
			s += i;
			value += i*25;
			for( j=0 ; j<=c && s+j<total && value+j*10<=a; j++ )
			{
				s += j;
				value += j*10;
				for( k=0 ; k<=d && s+k<total && value+k*5<=a; k++ )
				{
					s += k;
					value += k*5;
					if( a-value<=e && s+a-value < total )
					{
						total = s+a-value;
						as=i,bs=j,cs=k,ds=a-value;
					}
					s -= k;
					value -= k*5;
				}
				s -= j;
				value -= j*10;
			}
			s -= i;
			value -= i*25;
		}

		if( total == 99999 )
			printf( "NO EXACT CHANGE\n" );
		else printf( "%d %d %d %d\n", as, bs, cs, ds );
	}
	return 0;
}