AOJ201～210

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

0204　UFO Shooting Down Operation

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0204
ＵＦＯ撃墜ゲームの自動迎撃システムの撃墜シミュレーションをせよという問題です。

解法
この問題は当たり判定の数学的記述ができるかどうだけです。
三角関数と正射影の概念を使ってcalc関数で当たり判定を簡潔に記述します。
後は移動処理、ビームの半径内に入った機体の削除処理、ビームの当たり処理、削除処理を記述します。

、

#include<stdio.h>
#include<math.h>
#include<vector>
#include <algorithm>
struct enemy{
double x,y,len,moveX,moveY,r,v;
void setData(double sx,double sy,double size,double sv){
	len=sqrt(sx*sx+sy*sy);
	moveX=-sv*sx/len;
	moveY=-sv*sy/len;
	x=sx;
	y=sy;
	r=size;
	v=sv;
}
void move(){
	x+=moveX;
	y+=moveY;
	len-=v;
}
bool operator<(const enemy e)const{
	return len<e.len;
}
};
bool calc(double bx,double by,double rb,double ex,double ey,double re){
double len1=sqrt(bx*bx+by*by);
double lenSin=fabs(bx*ey-ex*by)/len1;
if(re<lenSin) return false;
double lenCos=(bx*ex+by*ey)/len1;
double len2=sqrt(re*re-lenSin*lenSin);
double ans=lenCos+len2;
if(ans<=rb)return false;
return true;
}
void setData(double R,int N){

std::vector<enemy> enemys;
std::vector<enemy>::iterator it;
enemy e;
double x0,y0,r,v;
for(int i=0;i<N;i++){
	scanf("%lf %lf %lf %lf",&x0,&y0,&r,&v);
	e.setData(x0,y0,r,v);
	enemys.push_back(e);
}
int inCount=0;
double bx,by;
while(enemys.empty()==false){
	it=enemys.begin();
	while(it!=enemys.end()){
		//移動処理
		(*it).move();
		//レーザーの有効圏内を割ったので削除処理
		if((*it).len<=R){
			it=enemys.erase(it);
			inCount++;
		}else{
			it++;
		}
	}
	if(enemys.empty()) break;
	//一番近いＵＦＯに並べ替える
	std::sort(enemys.begin(),enemys.end());
	it=enemys.begin();
	bx=(*it).x;
	by=(*it).y;
	while(it!=enemys.end()){
		//ビームの射線上に他に当たり判定がないか確かめて敵を削除する。
		if(calc(bx,by,R,(*it).x,(*it).y,(*it).r)){
			it=enemys.erase(it);
		}else{
			it++;
		}
	}
}
printf("%d\n",inCount);
}
int main(){
double R;
int N;
while(1){
	scanf("%lf %d",&R,&N);
	if(R==0 && N==0) break;
	setData(R,N);
}
}

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

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0208

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

#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");
}
}

0209　Scene in a Picture

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0209
２つの画像データを照合して一致する左上の座標を返す問題。

解法
普通に左上から画像を照合するだけです。

#include<stdio.h>
void roundPict(int rPict[4][51][51],int r,int m){
for(int y=0;y<m;y++){
	for(int x=0;x<m;x++){
		rPict[r][x][m-y-1]=rPict[r-1][y][x];
	}
}
}
void getPictTop(int rPict[4][51][51],int m,int xTops[4],int yTops[4]){
for(int r=0;r<4;r++){
	bool hit=false;
	for(int y=0;y<m;y++){
		for(int x=0;x<m;x++){
			if(rPict[r][y][x]!=-1){
				xTops[r]=x;
				yTops[r]=y;
				hit=true;
				break;
			}
		}
		if(hit==true)break;
	}
}
}
bool setData(){
int rPict[4][51][51],map[101][101],n,m;
int xTops[4],yTops[4];
scanf("%d %d",&n,&m);
if(n==0 && m==0) return false;

for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
		scanf("%d",&map[i][j]);
	}
}
for(int i=0;i<m;i++){
	for(int j=0;j<m;j++){
		scanf("%d",&rPict[0][i][j]);
	}
}
roundPict(rPict,1,m);
roundPict(rPict,2,m);
roundPict(rPict,3,m);
getPictTop(rPict,m,xTops,yTops);
int side=n-m+1;
bool hit;
int ansX=101,ansY=101,tx,ty;
	for(int y=0;y<side;y++){
		if(ansY<y) break;
		for(int x=0;x<side;x++){
			for(int r=0;r<4;r++){
			hit=true;
			for(int dy=0;dy<m;dy++){
				for(int dx=0;dx<m;dx++){
					if(rPict[r][dy][dx]!=-1 && rPict[r][dy][dx]!=map[y+dy][x+dx]){
						hit=false;
						break;
					}
				}
				if(hit==false) break;
			}
			if(hit==true){
				tx=x+xTops[r];
				ty=y+yTops[r];
				if(ansY>ty || (ansY==ty && ansX>tx)){
					ansY=ty;
					ansX=tx;
				}
			}
		}
	}
}
if(ansY==101){
	printf("NA\n");
}else{
	printf("%d %d\n",ansX+1,ansY+1);
}
return true;
}
int main(){
while(setData()){
}
}

タグ：

+ タグ編集

「AOJ201～210」をウィキ内検索

最終更新：2011年09月27日 14:54

c21coterie @ ウィキ

更新履歴

メニュー

リンク

他のサービス

0201　Wrought Gold Master

0202　At Boss's Expense

0203　A New Plan of Aizu Ski Resort

0204　UFO Shooting Down Operation

0205　Rock, Paper, Scissors

0206　Next Trip

0207　Block

0208　Room Numbers of a Hospital

0209　Scene in a Picture

c21coterie @ ウィキ

AOJ201～210

更新履歴

メニュー

リンク

他のサービス

0201 Wrought Gold Master

0202 At Boss's Expense

0203 A New Plan of Aizu Ski Resort

0204 UFO Shooting Down Operation

0205 Rock, Paper, Scissors

0206 Next Trip

0207 Block

0208 Room Numbers of a Hospital

0209 Scene in a Picture

0201　Wrought Gold Master

0202　At Boss's Expense

0203　A New Plan of Aizu Ski Resort

0204　UFO Shooting Down Operation

0205　Rock, Paper, Scissors

0206　Next Trip

0207　Block

0208　Room Numbers of a Hospital

0209　Scene in a Picture