Codeforces Round 218(Div.2 Only) C. Hamburgers

Codeforces

問題

ハンバーガーのレシピがあります。要するに１つのハンバーガーを作るのに
・パン
・ソーセージ
・チーズ
の３つの材料がそれぞれ何個ずつ要るかが文字列sとして与えられます。
手持ちの３つの材料の数ns,ns,ncと、
３つの材料を買い足す場合の単価pb,ps,pc、
そして所持金rが与えられます。

所持金の範囲でいくらでも材料を買い足せるとして、最大何個のハンバーガーを作れるでしょう？

制約
1≦ns,ns,nc≦100
1≦ps,ps,pc≦100
1≦r≦10^12


解法

作れるハンバーガーの数は、
たとえばパン１つだけ、というレシピでns=100, ps=1, r=10^12のときが最高で10^12+100です。

ということで高々こんなものであれば二分探索で「n個のハンバーガーを作ることはできるか？」を見ていくことで答えにたどり着けます。
これはn個作るのに材料がいくら足りないからいくら掛かる、ということを計算してrと比較すれば求まります。

自分は二分探索するのが面倒だったので、
「最初の手持ちで作れるハンバーガーは高々100個」という性質を使って、
101個以上作るときは全部買い足し食材になるので100作った時点で残ってる所持金をハンバーガー材料の値段で割って計算し、
100個以下しか作れないときは線形探索していました。

プログラム

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
#include<ctime>
#include<set>
using namespace std;


#define li			long long int
#define rep(i,to)	for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)	for(li i=(li)(start);i<((li)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 100000000
#define F first
#define S second
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

#define INFF 1000000000000

li kos(li kosu, li need){
	if(need==0)return INFF;
	return kosu/need;
}

	li b,s,c;
	li pb, ps, pc;
	li hb=0, hs=0, hc=0;
	li r;

bool ok(li n){
	li price=0;
	price+=max(0ll, (hb*n-b)*pb);
	price+=max(0ll, (hs*n-s)*ps);
	price+=max(0ll, (hc*n-c)*pc);
	return r-price>=0;
}

int main(){
	string recipe;

	cin>>recipe;
	cin>>b>>s>>c;
	cin>>pb>>ps>>pc;
	cin>>r;

	rep(i,sz(recipe)){
		hb+=(recipe[i]=='B');
		hs+=(recipe[i]=='S');
		hc+=(recipe[i]=='C');
	}

	li res=0;
	li sb,ss,sc;
	li ma=101;

	li ccc=0;
	ccc+=max((ma*hb-b)*pb,0ll);
	ccc+=max((ma*hc-c)*pc,0ll);
	ccc+=max((ma*hs-s)*ps,0ll);
	if(ccc<=r){
		res=ma;
		r-=ccc;
		res+=r/(hb*pb+hs*ps+hc*pc);
		cout<<res<<endl;
		return 0;
	}

	res=0;
	repp(i,1,101){
		if(ok(i)){
			res=i;
		}
		else break;
	}
	cout<<res<<endl;

	return 0;
}