読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #218 Div2. C. Hamburgers

CF218はDiv2 Onlyなのでunofficialで参加。
少し遅れて参加したけど、無事全問正解。Div2とはいえ本番全問正解は初めてかな。
優しめのセットだったとはいえ、pretestのミスも全体で1回だし、良い出来だった。
http://codeforces.com/contest/371/problem/C

問題

1つのハンバーガーを作るレシピとして、必要なバンズ・パティ・チーズの数が与えられる。
今店にあるバンズ・パティ・チーズの数と、それぞれ新たに1個買う場合の金額がわかっている。
お金をR持っている場合、手持ちの材料と合わせて最大何個ハンバーガーを作れるか答えよ。

解法

手持ちの材料が全部なくなるまでは、1個ずつハンバーガーを作っていく。
手持ちの材料は高々1000個なので、1000ループまでの間には材料が底を尽きる。
材料が尽きたら、後は1個のハンバーガーを作るのにかかるお金は、材料ごとの(必要個数×単価)の和になるので、残るお金を1個当たりのお金で割ればよい。

string S;
int N[3],P[3],NN[3];
ll R;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>S;
	cin>>N[0]>>N[1]>>N[2];
	cin>>P[0]>>P[1]>>P[2];
	cin>>R;
	FOR(i,S.size()) {
		if(S[i]=='B') NN[0]++;
		if(S[i]=='S') NN[1]++;
		if(S[i]=='C') NN[2]++;
	}
	
	ll res=0;
	while(1) {
		if((!NN[0] || (N[0]==0)) && (!NN[1] || (N[1]==0)) && (!NN[2] || (N[2]==0))) {
			x=P[0]*NN[0]+P[1]*NN[1]+P[2]*NN[2];
			res += R/x;
			break;
		}
		x=0;
		FOR(i,3) {
			if(N[i]>=NN[i]) N[i]-=NN[i];
			else x+=P[i]*(NN[i]-N[i]),N[i]=0;
		}
		if(R<x) break;
		R-=x;
		res++;
	}
	cout << res << endl;
}

問題

手持ちの材料のオーダーをO(N)で処理できない10^7とかにしたら、もう少しややこしい問題になるのにな。

広告を非表示にする