「AOJ71～80」の編集履歴（バックアップ）一覧はこちら

「AOJ71～80」(2011/08/29 (月) 13:19:05) の最新版変更点

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

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

*0071　Bombs Chain
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0071
ボンバーマンルールで升目に爆弾と床のデータが与えれます。
爆弾は爆発すると上下3マス左右3マス以内にある爆弾も爆発し連鎖します。
爆弾の配置と最初に爆発する爆弾が与えられるので、爆発後のマップの状態を計算せよという問題。
解法
マップが小さいので深さ優先探索で気楽に実装します。
マップの外にはみ出さないように注意するくらいです。



 #include<stdio.h>
 char map[9][9];
 void saiki(int x,int y){
	int nx,ny;
	for(int i=-3;i<4;i++){
		nx=x+i;
		ny=y;
		if(8>nx && nx>-1 && map[ny][nx]=='1'){
			map[ny][nx]='0';
			saiki(nx,ny);
		}
		nx=x;
		ny=y+i;
		if(ny>7 || ny<0) continue;
		if(map[ny][nx]=='1'){
			map[ny][nx]='0';
			saiki(nx,ny);
		}
	}
 }
 void setMap(int no){
	for(int i=0;i<8;i++){
		scanf("%s",map[i]);
	}
	int sx,sy;
	scanf("%d %d",&sx,&sy);
	saiki(sx-1,sy-1);
	printf("Data %d:\n",no+1);

	for(int i=0;i<8;i++){
		printf("%s\n",map[i]);
	}
 }
 int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		setMap(i);
	}
 }






----
*0072　Carden Lantern
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0072
複数の史跡とそれをつなぐ道路の長さがある、観光事業の一環として史跡をつなぐ道路の100ｍ事に灯篭を設置することになった。
全ての史跡をつなげつつ、ランタンの数を最小にするにはどうすればよいかという問題。

解法
典型的なプリム法の問題です。
最初に解いた時はプリム法を知らず、プリム法と同じ方法を自力で思いついて実装したのでコードが上手くいくかドキドキものだった印象的な問題です。
その時のコードは正解でした。
ここに掲載のコードは最初のコードの高速化を目指して少しコードを弄っています。


 #include<stdio.h>
 #include<queue>
 #include<vector>
 struct load{
	int p1,p2,len;
	bool operator<(const load l)const{
		return len>l.len;
	}
 };
 void setMap(int n,int m){
	int points[101]={0};
	std::priority_queue<load> loads;
	std::vector<load> map[101];
	std::vector<load>::iterator it,end;
	load l,start;
	start.len=2000000000;
	for(int i=0;i<m;i++){
		scanf("%d,%d,%d",&l.p1,&l.p2,&l.len);
		l.len=l.len/100-1;
		map[l.p1].push_back(l);
		map[l.p2].push_back(l);
		start=l.len<start.len?l:start;
	}
	int count=1,ans=0,addOK;
	loads.push(start);
	while(n>count && loads.empty()==false){
		l=loads.top();
		loads.pop();
		addOK=false;
		if(points[l.p1]==0){
			addOK=true;
			points[l.p1]=1;
			it=map[l.p1].begin();
			end=map[l.p1].end();
			while(it!=end){
				loads.push(*it);
				it++;
			}
		}
		if(points[l.p2]==0){
			addOK=true;
			points[l.p2]=1;
			it=map[l.p2].begin();
			end=map[l.p2].end();
			while(it!=end){
				loads.push(*it);
				it++;
			}
		}
		if(addOK==true){
			count++;
			ans+=l.len;
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	int n,m;
	scanf("%d",&n);
	while(n!=0){
		scanf("%d",&m);
		setMap(n,m);
		scanf("%d",&n);
	}
 }






----
*0073　Surface Area of Quadrangular Pyramid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0073
教科書通りに書くだけ。


 #include<stdio.h>
 #include<math.h>
 int main(){
	double x,h;
	while(1){
		scanf("%lf %lf",&x,&h);
		if(x==0&&h==0) break;
		printf("%lf\n",x*(x+2*sqrt(h*h+x*x/4.0)));
	}
 }



----
*0074　Videotape
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0074
ビデオテープの録画済み時間が与えられる。
残りを普通取りした時と3倍撮りした時の残り時間を計算せよという問題。
解法
ただ単に残り秒数を求めてmod演算で時、分、秒を表示するだけです。


 #include<stdio.h>
 int main(){
	int h,m,s,max=7200,t,u;
	while(1){
		scanf("%d %d %d",&h,&m,&s);
		if(h==-1 && m==-1 && s==-1) break;
		u=h*3600+m*60+s;
		t=max-u;
		printf("%02d:%02d:%02d\n",t/3600,t%3600/60,t%60);
		t*=3;
		printf("%02d:%02d:%02d\n",t/3600,t%3600/60,t%60);
	}
 }






----
*0075 ＢＭＩ
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0075
伸長と体重のデータが与えられるのでＢＭＩが25以上の人を表示せよという問題。
解法
ただ計算して表示するかしないかを決めるだけです。


 #include<stdio.h>
 int main(){
	int no;
	double kg,m;
	while(scanf("%d,%lf,%lf",&no,&kg,&m)!=EOF){
		kg/(m*m)>=25?printf("%d\n",no):m;
	}
 }






----
*0076　Treasure Hunt II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0076
宝のありかを記した記録があり、その記録通りに移動した時の座標を表示せよという問題。
解法
ベクトルと回転行列を使って一手事に計算して記録していくだけです。


 #include<stdio.h>
 #include<math.h>
 int main(){
	double xs[1001],ys[1001],len;
	xs[0]=1;
	ys[0]=0;
	for(int i=1;i<1001;i++){
		len=sqrt(xs[i-1]*xs[i-1]+ys[i-1]*ys[i-1]);
		xs[i]=-ys[i-1]/len+xs[i-1];
		ys[i]=xs[i-1]/len+ys[i-1];
	}
	int n;
	while(1){
		scanf("%d",&n);
		if(n==-1)break;
		printf("%lf\n%lf\n",xs[n-1],ys[n-1]);
	}
 }




----
*0077　Run Length
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0077
ある文字が連続している場合それを@、文字数、文字で圧縮した文字列が与えられる。
これを復号化せよという問題。

解法
変換するパイプに通すだけでできます。
@を見つけたら2つ次の文字を一つ次の数字だけ出力しポインタを2つ進める。
普通の文字ならそのまま出力して次の文字へ。

 #include<stdio.h>
 #include<string.h>
 int main(){
	char text[101];
	while(scanf("%s",text)!=EOF){
		int len=strlen(text);
		for(int i=0;i<len;i++){
			if(text[i]=='@'){
				for(int j=0;j<text[i+1]-'0';j++){
					printf("%c",text[i+2]);
				}
				i+=2;
			}else{
				printf("%c",text[i]);
			}
		}
		printf("\n");
	}
 }






*0078　Magic Square
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0078
整数ｎが与えられるのでｎ*ｎサイズの魔法陣を出力せよという問題。
解法
問題の方で魔法陣の生成アルゴリズムが指定されているのでそのままコード化します。
書いてある通りにいかに短い時間で記述できるかを試される問題です。

 #include<stdio.h>
 void set(int n){
	int map[15][15]={0},size=n*n,x,y,i;
	x=y=n/2;	
	y++;
	map[y][x]=1;
	i=1;
	while(i<size){
		x=(x+1)%n;
		y=(y+1)%n;
		i++;
		if(map[y][x]==0){
			map[y][x]=i;
		}else{
			x=(x+n-1)%n;
			y=(y+1)%n;
			map[y][x]=i;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)printf("%4d",map[i][j]);
		printf("\n");
	}
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n!=0){
		set(n);
		scanf("%d",&n);
	}
 }






----
*0079　Area of Polygon
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0079
凸ｎ角形の頂点座標が与えられるので、その面積を答えよという問題。
解法
ベクトルの教科書通りに三角形の面積を求める式を書くだけです。

 #include<stdio.h>
 int main(){
	double xs[2],ys[2],ans=0,sx,sy;
	int i=1;
	scanf("%lf,%lf",&sx,&sy);
	xs[0]=sx;
	ys[0]=sy;
	while(scanf("%lf,%lf",&xs[i],&ys[i])!=EOF){
		i++;
		i%=2;
		ans+=(xs[i]-xs[(i+1)%2])*(ys[i]+ys[(i+1)%2]);
	}
	ans+=(xs[(i+1)%2]-sx)*(sy+ys[(i+1)%2]);
	ans/=2;
	printf("%lf\n",ans<0?-ans:ans);
 }



----
*0080　Third Root
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0080
ｘ＾３＝qのｑよりｘを求める漸化式が指定されています。
指示通りの処理をするプログラムを書いてください。
解法
指示通りに実装するだけです。


 #include<stdio.h>
 #include<math.h>
 int main(){
	double x,q;
	scanf("%lf",&q);
	while(q!=-1){
		x=q/2.0;
		while(fabs(x*x*x-q)>=0.00001*q){
			x=x-(x*x*x-q)/(3*x*x);
		}
		printf("%lf\n",x);
		scanf("%lf",&q);
	}
 }

*0071　Bombs Chain
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0071
ボンバーマンルールで升目に爆弾と床のデータが与えれます。
爆弾は爆発すると上下3マス左右3マス以内にある爆弾も爆発し連鎖します。
爆弾の配置と最初に爆発する爆弾が与えられるので、爆発後のマップの状態を計算せよという問題。
解法
マップが小さいので深さ優先探索で気楽に実装します。
マップの外にはみ出さないように注意するくらいです。



 #include<stdio.h>
 char map[9][9];
 void saiki(int x,int y){
	int nx,ny;
	for(int i=-3;i<4;i++){
		nx=x+i;
		ny=y;
		if(8>nx && nx>-1 && map[ny][nx]=='1'){
			map[ny][nx]='0';
			saiki(nx,ny);
		}
		nx=x;
		ny=y+i;
		if(ny>7 || ny<0) continue;
		if(map[ny][nx]=='1'){
			map[ny][nx]='0';
			saiki(nx,ny);
		}
	}
 }
 void setMap(int no){
	for(int i=0;i<8;i++){
		scanf("%s",map[i]);
	}
	int sx,sy;
	scanf("%d %d",&sx,&sy);
	saiki(sx-1,sy-1);
	printf("Data %d:\n",no+1);
	for(int i=0;i<8;i++){
		printf("%s\n",map[i]);
	}
 }
 int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		setMap(i);
	}
 }






----
*0072　Carden Lantern
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0072
複数の史跡とそれをつなぐ道路の長さがある、観光事業の一環として史跡をつなぐ道路の100ｍ事に灯篭を設置することになった。
全ての史跡をつなげつつ、ランタンの数を最小にするにはどうすればよいかという問題。

解法
典型的なプリム法の問題です。
最初に解いた時はプリム法を知らず、プリム法と同じ方法を自力で思いついて実装したのでコードが上手くいくかドキドキものだった印象的な問題です。
その時のコードは正解でした。
ここに掲載のコードは最初のコードの高速化を目指して少しコードを弄っています。


 #include<stdio.h>
 #include<queue>
 #include<vector>
 struct load{
	int p1,p2,len;
	bool operator<(const load l)const{
		return len>l.len;
	}
 };
 void setMap(int n,int m){
	int points[101]={0};
	std::priority_queue<load> loads;
	std::vector<load> map[101];
	std::vector<load>::iterator it,end;
	load l,start;
	start.len=2000000000;
	for(int i=0;i<m;i++){
		scanf("%d,%d,%d",&l.p1,&l.p2,&l.len);
		l.len=l.len/100-1;
		map[l.p1].push_back(l);
		map[l.p2].push_back(l);
		start=l.len<start.len?l:start;
	}
	int count=1,ans=0,addOK;
	loads.push(start);
	while(n>count && loads.empty()==false){
		l=loads.top();
		loads.pop();
		addOK=false;
		if(points[l.p1]==0){
			addOK=true;
			points[l.p1]=1;
			it=map[l.p1].begin();
			end=map[l.p1].end();
			while(it!=end){
				loads.push(*it);
				it++;
			}
		}
		if(points[l.p2]==0){
			addOK=true;
			points[l.p2]=1;
			it=map[l.p2].begin();
			end=map[l.p2].end();
			while(it!=end){
				loads.push(*it);
				it++;
			}
		}
		if(addOK==true){
			count++;
			ans+=l.len;
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	int n,m;
	scanf("%d",&n);
	while(n!=0){
		scanf("%d",&m);
		setMap(n,m);
		scanf("%d",&n);
	}
 }






----
*0073　Surface Area of Quadrangular Pyramid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0073
四角すいの高さと底面のデータが与えられるので表面積を求めよという問題。
解法
教科書通りに書くだけで済みます。


 #include<stdio.h>
 #include<math.h>
 int main(){
	double x,h;
	while(1){
		scanf("%lf %lf",&x,&h);
		if(x==0&&h==0) break;
		printf("%lf\n",x*(x+2*sqrt(h*h+x*x/4.0)));
	}
 }



----
*0074　Videotape
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0074
ビデオテープの録画済み時間が与えられる。
残りを普通取りした時と3倍撮りした時の残り時間を計算せよという問題。
解法
ただ単に残り秒数を求めてmod演算で時、分、秒を表示するだけです。


 #include<stdio.h>
 int main(){
	int h,m,s,max=7200,t,u;
	while(1){
		scanf("%d %d %d",&h,&m,&s);
		if(h==-1 && m==-1 && s==-1) break;
		u=h*3600+m*60+s;
		t=max-u;
		printf("%02d:%02d:%02d\n",t/3600,t%3600/60,t%60);
		t*=3;
		printf("%02d:%02d:%02d\n",t/3600,t%3600/60,t%60);
	}
 }






----
*0075 ＢＭＩ
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0075
伸長と体重のデータが与えられるのでＢＭＩが25以上の人を表示せよという問題。
解法
ただ計算して表示するかしないかを決めるだけです。


 #include<stdio.h>
 int main(){
	int no;
	double kg,m;
	while(scanf("%d,%lf,%lf",&no,&kg,&m)!=EOF){
		kg/(m*m)>=25?printf("%d\n",no):m;
	}
 }






----
*0076　Treasure Hunt II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0076
宝のありかを記した記録があり、その記録通りに移動した時の座標を表示せよという問題。
解法
ベクトルと回転行列を使って一手事に計算して記録していくだけです。


 #include<stdio.h>
 #include<math.h>
 int main(){
	double xs[1001],ys[1001],len;
	xs[0]=1;
	ys[0]=0;
	for(int i=1;i<1001;i++){
		len=sqrt(xs[i-1]*xs[i-1]+ys[i-1]*ys[i-1]);
		xs[i]=-ys[i-1]/len+xs[i-1];
		ys[i]=xs[i-1]/len+ys[i-1];
	}
	int n;
	while(1){
		scanf("%d",&n);
		if(n==-1)break;
		printf("%lf\n%lf\n",xs[n-1],ys[n-1]);
	}
 }




----
*0077　Run Length
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0077
ある文字が連続している場合それを@、文字数、文字で圧縮した文字列が与えられる。
これを復号化せよという問題。

解法
変換するパイプに通すだけでできます。
@を見つけたら2つ次の文字を一つ次の数字だけ出力しポインタを2つ進める。
普通の文字ならそのまま出力して次の文字へ。

 #include<stdio.h>
 #include<string.h>
 int main(){
	char text[101];
	while(scanf("%s",text)!=EOF){
		int len=strlen(text);
		for(int i=0;i<len;i++){
			if(text[i]=='@'){
				for(int j=0;j<text[i+1]-'0';j++){
					printf("%c",text[i+2]);
				}
				i+=2;
			}else{
				printf("%c",text[i]);
			}
		}
		printf("\n");
	}
 }





----
*0078　Magic Square
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0078
整数ｎが与えられるのでｎ*ｎサイズの魔法陣を出力せよという問題。
解法
問題の方で魔法陣の生成アルゴリズムが指定されているのでそのままコード化します。
書いてある通りにいかに短い時間で記述できるかを試される問題です。

 #include<stdio.h>
 void set(int n){
	int map[15][15]={0},size=n*n,x,y,i;
	x=y=n/2;	
	y++;
	map[y][x]=1;
	i=1;
	while(i<size){
		x=(x+1)%n;
		y=(y+1)%n;
		i++;
		if(map[y][x]==0){
			map[y][x]=i;
		}else{
			x=(x+n-1)%n;
			y=(y+1)%n;
			map[y][x]=i;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)printf("%4d",map[i][j]);
		printf("\n");
	}
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n!=0){
		set(n);
		scanf("%d",&n);
	}
 }






----
*0079　Area of Polygon
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0079
凸ｎ角形の頂点座標が与えられるので、その面積を答えよという問題。
解法
ベクトルの教科書通りに三角形の面積を求める式を書くだけです。

 #include<stdio.h>
 int main(){
	double xs[2],ys[2],ans=0,sx,sy;
	int i=1;
	scanf("%lf,%lf",&sx,&sy);
	xs[0]=sx;
	ys[0]=sy;
	while(scanf("%lf,%lf",&xs[i],&ys[i])!=EOF){
		i++;
		i%=2;
		ans+=(xs[i]-xs[(i+1)%2])*(ys[i]+ys[(i+1)%2]);
	}
	ans+=(xs[(i+1)%2]-sx)*(sy+ys[(i+1)%2]);
	ans/=2;
	printf("%lf\n",ans<0?-ans:ans);
 }



----
*0080　Third Root
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0080
ｘ＾３＝qのｑよりｘを求める漸化式が指定されています。
指示通りの処理をするプログラムを書いてください。
解法
指示通りに実装するだけです。


 #include<stdio.h>
 #include<math.h>
 int main(){
	double x,q;
	scanf("%lf",&q);
	while(q!=-1){
		x=q/2.0;
		while(fabs(x*x*x-q)>=0.00001*q){
			x=x-(x*x*x-q)/(3*x*x);
		}
		printf("%lf\n",x);
		scanf("%lf",&q);
	}
 }