Codeforces 69 C. Game

問題

k人の仲間がいる。
店で買える基礎アーティファクトがn個あり、
合成によりできる合成アーティファクトがm個あり、それぞれのレシピが与えられる。
q個の購入するアーティファクトおよび購入者のリストが与えられる。

アーティファクトが合成できるようになった時点で、
アーティファクトを合成するものとする。
全部の購入が終わった後でのそれぞれの仲間の持っているアーティファクトを出力せよ。

制約条件

k≦100
n,m≦50
q≦500

方針

1個購入するごとにナイーブに合成できるアーティファクトがあるか調べればよい。

ソースコード

int k,n,m,q;
map<string,int> M;

void run()
{
	M.clear();
	string in,name;
	getline(cin,in);
	{
		stringstream ss(in);
		ss>>k>>n>>m>>q;
	}
	int l=0;
	rep(i,n){
		getline(cin,in);
		if(!M.count(in))M[in]=l++;
	}
	vector<pair<int,vector<pi> > > recipe;
	
	rep(i,m){
		getline(cin,in);
		int p=in.find(":");
		name=in.substr(0,p);
		if(!M.count(name))M[name]=l++;
		int cur=M[name],t;
		in=in.substr(p+2);
		
		vector<pi> tmp;
		
		for(;;){
			p=in.find(",");
			stringstream ss(in.substr(0,p));
			ss>>name>>t;
			tmp.pb(mp(M[name],t));
			if(p==string::npos)break;
			in=in.substr(p+2);
		}
		recipe.pb(mp(cur,tmp));
	}
	
	
	vector<vi> a(k,vi(M.size()));
	rep(i,q){
		int t; cin>>t>>name;
		a[--t][M[name]]++;
		
		rep(j,recipe.size()){
			bool ok=1;
			rep(k,recipe[j].second.size())
				ok&=a[t][recipe[j].second[k].first]>=recipe[j].second[k].second;
			if(ok){
				rep(k,recipe[j].second.size())
					a[t][recipe[j].second[k].first]-=recipe[j].second[k].second;
				a[t][recipe[j].first]++;
			}
		}
	}
	vector<string> N(M.size());
	fr(i,M)N[i->second]=i->first;
	
	rep(i,k){
		vector<pair<string,int> > ans;
		rep(j,M.size())if(a[i][j]>0)ans.pb(mp(N[j],a[i][j]));
		sort(all(ans));
		cout<<ans.size()<<endl;
		rep(j,ans.size())cout<<ans[j].first<<" "<<ans[j].second<<endl;
	}
}