※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「AOJ201~210」の編集履歴(バックアップ)一覧に戻る

AOJ201~210 - (2011/09/02 (金) 11:03:30) のソース

*0201 Wrought Gold Master
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0201
錬金術でアイテムの調合ができます。
複数のアイテムを調合して最も安く目的のアイテムを作ったときの値段を求める問題。

解法
アイテムを一つずつ確かめて、連金で安くなるならその値段に改定します。
改定した値段で更に調べなおして、値段が改定できなくなるまでループし続ければ答えがもとまります。
この方法でも十分速度はでますが、すべてのアイテムの最低値を求めいており無駄があります。
もっと賢い方法として両手法という方法があるようです。



 #include<iostream>
 #include<map>
 #include<string>
 #include<vector>
 using namespace std;
 void setData(int n){	
	map<string,int> items;
	map<string,vector<string> > process;
	map<string,int>::iterator itemIt;
	vector<string>::iterator processIt,end;
	int Count=1,value,m,k,sum;
	string name,item;	
	for(int i=0;i<n;i++){
		std::cin>>name>>value;
		items[name]=value;
	}
	std::cin>>m;
	for(int i=0;i<m;i++){
		std::cin>>name>>k;
		for(int i=0;i<k;i++){
			cin>>item;
			process[name].push_back(item);
		}
	}
	cin>>name;
	while(Count>0){
		Count=0;
		itemIt=items.begin();
		while(itemIt!=items.end()){
			sum=0;
			if(process.find((*itemIt).first)!=process.end()){
				processIt=process[(*itemIt).first].begin();
				end=process[(*itemIt).first].end();
				while(processIt!=end){
					sum+=items[*processIt];
					processIt++;
				}
				if(sum<(*itemIt).second){
					items[(*itemIt).first]=sum;
					Count++;
				}
			}
			itemIt++;
		}
	}
	cout<<items[name]<<"\n";
 }
 int main(){
	int n;
	while(scanf("%d",&n),n>0){
		setData(n);
	}
 }






----
*0202 At Boss's Expense
飲食店で食べ物の値段と予算が与えられます。
食べ物を組み合わせて、予算額以下で素数になっている注文額を求めよという問題。
1円は特例的に素数に含むようです。

解法
下から足しこんでいくだけです。
値段1円のものがあったら計算量が増えるのでその時は全ての値段を作ることができることを逆利用して上から見ていきます。
普通の値段なら下から足しこんでいくだけです。
重複して足しこんでいる部分があるので重複を削除できればもう少し高速化できるかもしれません。


 #include<stdio.h>
 #include<string.h>
 #include <algorithm>
 int so[1000002];
 void setSo(){
	for(int i=2;i<1000001;i++)
		so[i]=i%2;
	int k;
	for(int i=3;i<=1000;i+=2){
		if(so[i]==true){
			k=i*2;
			for(int j=i*3;j<1000001;j+=(k)){
				so[j]=false;
			}
		}
	}
	so[0]=false;
	so[1]=true;
	so[2]=true;
 }
 bool permMemo[1000002];
 void calc(int n,int x){
	int foods[31],ans=-1,t;
	bool isOne=false;
	for(int i=0;i<n;i++){
		scanf("%d",&foods[i]);
		if(foods[i]==1) isOne=true;
	}
	if(isOne==true){
		//1があったので最大の素数を求める
		for(int i=x;i>0;i--){
			if(so[i]==true){
				ans=i;
				break;
			}
		}
	}else{
		memset(permMemo,false,x+1);
		permMemo[0]=true;
		std::sort(foods,foods+n);
		for(int i=0;i<x;i++){
			//0から値段を一つずつ足しこんでいく
			if(permMemo[i]==true){
				for(int j=0;j<n;j++){
					t=i+foods[j];
					if(x<t)break;
					permMemo[t]=true;
					if(so[t]==true){
						ans=t>ans?t:ans;
					}
				}
			}
		}
	}
	if(ans==-1){
		printf("NA\n");
	}else{
		printf("%d\n",ans);
	}
 }
 int main(){
	int n,x;
	setSo();
	while(scanf("%d %d",&n,&x),n+x>0){
		calc(n,x);
	}
 }