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

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

AOJ201~210 - (2011/09/02 (金) 11:00:20) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

 *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);
 	}
  }