2709 Painter

問題概要

絵の具のセット一つにはN色の絵の具がそれぞれ50mlずつ入っている。
異なる3色の絵の具をxmlずつ混ぜるとxmlのグレーの絵の具を作ることができる。

各色の必要量および、グレーの色の必要量が与えられるとき、
絵の具のセットを購入しなければならない最小の数を求めよ。

N≦12,それぞれの絵の具の必要量≦1000を満たす。

解法

グレーの絵の具を1ml作るには、余っている絵の具を量の多い順に使えばよい。

絵の具の量は小さいので、
上の操作をグレーの絵の具の量の回数、絵の具の量をソートしながら繰り返す解法で通る。

ソースコード

int n,g,in[12],ans,t;
void func(){
	sort(in,in+n,greater<int>());
	if(in[2]==0)
	{
		ans++;
		rep(i,n)in[i]+=50;
	}
	in[0]--; in[1]--; in[2]--;
}

int main()
{
	while(scanf("%d",&n),n)
	{
		ans=0;
		rep(i,n)
		{
			scanf("%d",in+i);
			ans=max(ans,in[i]/50+(in[i]%50!=0));
		}
		scanf("%d",&g);
		
		rep(i,n)
		{
			in[i]=ans*50-in[i];
		}
		rep(i,g)func();
		printf("%d\n",ans);
	}
	return 0;
}