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

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

AOJ201~210 - (2011/09/02 (金) 12:08:30) の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);
 	}
  }
 
 
 
 ----
 *0203 A New Plan of Aizu Ski Resort
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0203
 スキー場のマップが格子で与えられるので何通りの滑り方があるか答える問題。
 解法
 一段ずつ前の段から計算してルート数を求め最後に集計するだけです。
 最後の集計は最終行をジャンプ台で飛ばしてる場合があるので一行先まで集計します。
 ジャンプ台杉ジャンプ台のようなパターンがあるのでその点にだけ注意すれば簡単な問題です。
 
 
 
 
  #include<stdio.h>
  #include<string.h>
  int   map[16][18];
  int roots[18][18];
  void setMap(int x,int y){
 	memset(map,0,16*18*4);
 	for(int i=0;i<y;i++){
 		for(int j=1;j<=x;j++){
 			scanf("%d",&map[i][j]);
 		}
 	}
 	memset(roots,0,18*18*4);
 	for(int i=1;i<=x;i++){
 		if(map[0][i]==0){
 			roots[0][i]=1;
 		}
 	}
 	int t,r;
 	for(int i=0;i<y-1;i++){
 		for(int j=1;j<=x;j++){
 			t=map[i][j];
 			r=roots[i][j];
 			if(t==1){
 				//障害物なので何もしない
 				roots[i][j]=0;
 				continue;
 			}else if(t==2 && map[i+2][j]!=1){
 				//ジャンプ台かつジャンプ先が障害物でないなら
 				roots[i+2][j]+=r;
 			}else if(t==0){
 				//斜面なら
 				if(map[i+1][j-1]==0) roots[i+1][j-1]+=r;
 				if(map[i+1][j+0]!=1) roots[i+1][j+0]+=r;
 				if(map[i+1][j+1]==0) roots[i+1][j+1]+=r;
 			}
 		}
 	}
 	int sum=0;
 	for(int i=1;i<=x;i++) sum+=roots[y][i]+roots[y-1][i];
 	printf("%d\n",sum);
  }
  int main(){
 	int x,y;
 	while(scanf("%d %d",&x,&y),x+y>0){
 		setMap(x,y);
+	}
+ }
+
+
+
+
+
+----
+*0205 Rock, Paper, Scissors
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0205
+5人のじゃんけんの結果を表示せよという問題。
+
+解法
+グーを1チョキを2パーを4としてビット演算に符号化して解いてみました。
+この方法なら何人に増えても変数を変えるだけで対応できます。
+
+
+ #include<stdio.h>
+ int main(){
+	int te[5],kekka[4];
+	int all;
+	while(scanf("%d",&te[0]),te[0]!=0){
+		all=(1<<(te[0]-1));
+		for(int i=1;i<5;i++){
+			scanf("%d",&te[i]);
+			all|=(1<<(te[i]-1));
+		}
+		if(all==7 || all==4 || all==2 || all==1){
+			kekka[1]=kekka[2]=kekka[3]=3;
+		}else if(all==3){
+			//グーとチョキ
+			kekka[1]=1;
+			kekka[2]=2;
+		}else if(all==5){
+			//グーとパー
+			kekka[1]=2;
+			kekka[3]=1;
+		}else if(all==6){
+			//チョキとパー
+			kekka[2]=1;
+			kekka[3]=2;
+		}
+		for(int i=0;i<5;i++)printf("%d\n",kekka[te[i]]);
 	}
  }