c21coterie @ ウィキ
c21coterie @ ウィキ

「AOJ201～210」の編集履歴（バックアップ）一覧に戻る

AOJ201～210 - (2011/09/02 (金) 13:41:20) の編集履歴(バックアップ)

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





0206　Next Trip

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0206
月々の貯蓄から旅行費用の積み立てがいつ終わるかを答える問題。

解法
単純に足し算するだけの問題です。 

#include<stdio.h>
int main(){
int l,n,m,sum,ans;
while(scanf("%d",&l),l!=0){
	ans=sum=0;
	for(int i=0;i<12;i++){
		scanf("%d %d",&m,&n);
		sum+=m-n;
		if(sum>=l && ans==0){
			ans=i+1;
		}
	}
	if(ans==0){
		printf("NA\n");
	}else{
		printf("%d\n",ans);
	}
}
}






0207　Block

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0207
ブロックでできた迷路がスタートからゴールまでたどり着けるか調べる問題。

解法
奇麗に整え直したコードを掲載しようと思ったのですが、何故か簡単な問題なのにコードが通らず。
最初に書いたあまり良くないコードを掲載しておきます。
盤面を生成して再帰で探索しているだけです。
反面教師にでもしてください。 

#include <stdio.h>
void addBlock(int color,int d,int x,int y);
void setMap();
void search(int x,int y);
int map[102][102];
int xs,ys,xg,yg;
int w,h;
bool endFlag;
int startColor;
int main(){
scanf("%d %d",&w,&h);
while(w!=0 || h!=0){
	setMap();
	scanf("%d %d",&w,&h);
}
}
void setMap(){
for(int i=1;i<=h;i++){
	for(int j=1;j<=w;j++){
		map[i][j]=-1;
	}
}
endFlag=false;
scanf("%d %d",&xs,&ys);
scanf("%d %d",&xg,&yg);
int n;
scanf("%d",&n);
int c,d,x,y;
for(int i=0;i<n;i++){
	scanf("%d %d %d %d",&c,&d,&x,&y);
	addBlock(c,d,x,y);
}
startColor=map[xs][ys];
if(startColor!=-1){
	search(xs,ys);
}
if(endFlag==true)
{
	printf("OK\n");
}else{
	printf("NG\n");
}
}
void search(int x,int y){
if(w>=x && x>0 && h>=y && y>0){
if(map[x][y]!=-1 && map[x][y]==startColor){
	if(y==yg && x==xg){
		endFlag=true;
		return ;
	}	
	map[x][y]=-1;
	search(x+1,y);
	if(endFlag==true) return ;
	search(x-1,y);	
	if(endFlag==true) return ;
	search(x,y+1);
	if(endFlag==true) return ;
	search(x,y-1);	
	if(endFlag==true) return ;
}
}
}
void addBlock(int color,int d,int x,int y)
{
if(d==0){
	//横向き
	map[x][y]=map[x+1][y]=map[x+2][y]=map[x+3][y]=color;
	map[x][y+1]=map[x+1][y+1]=map[x+2][y+1]=map[x+3][y+1]=color;
}else{
	//縦向き
	map[x][y]=map[x][y+1]=map[x][y+2]=map[x][y+3]=color;
	map[x+1][y]=map[x+1][y+1]=map[x+1][y+2]=map[x+1][y+3]=color;
}
}




0208　Room Numbers of a Hospital


解法
私の考えたコードを掲載しようかと考えたのですがネットにとても美しい解法があったのでそちらを掲載することにしました。
簡単な問題を解くだけですが、シンプルで無駄がないいいコードです。 

#include<stdio.h>
//http://program.pinemz.net/article/168162542.htmlを参考にしました
int t[]={0,1,2,3,5,7,8,9};
void saiki(int n){
if(n>=8){
	saiki(n/8);
}
printf("%d",t[n%8]);
}
int main(){
int n;
while(scanf("%d",&n),n>0){
	saiki(n);
	printf("\n");
}
}