AOJ再挑戦71～75 - c21coterie @ ウィキ

問71　Bombs Chain

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0071
ボン○ーマンもどきの爆発連鎖を扱った問題。
解法
再帰以外思いつかなかった。

#include<stdio.h>
#include<string.h>

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

bool inArea(int x,int y){
	return (0<=x) && (x<8) && (0<=y) && (y<8);
}

void chain(char map[8][9],int x,int y){
	map[y][x]='0';
	for(int i=0;i<4;i++){
		for(int j=1;j<=3;j++){
			int nx=x+dx[i]*j;
			int ny=y+dy[i]*j;
			if(inArea(nx,ny)&&map[ny][nx]=='1'){
 				chain(map,nx,ny);
			}
		}
 	}
} 
 
void calc(int turn){
 	char map[8][9];
	for(int i=0;i<8;i++){
		scanf("%s",map[i]);
	}
 	int sx,sy;
 	scanf("%d %d",&sx,&sy);
	sx--;
	sy--;
	chain(map,sx,sy);
 	printf("Data %d:\n",turn);
	for(int i=0;i<8;i++){
		printf("%s\n",map[i]);
	}
} 
 
int main(){
	int n;
	scanf("%d",&n);
 	for(int i=1;i<=n;i++){
		calc(i);
 	}
}  

問72Carden Lantern

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0072
街路にランタンを設置する数を最小にする問題。
解法
最小全域木をプリム法で求めるだけです。

#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>

struct S{
   int to,cost;
   bool operator<(const S& s)const{
       return cost>s.cost;
   }
};

void calc(int n){
   int m,a,b,len;
   std::vector<S> G[101];
   std::priority_queue<S> pq;
   S s,s1;
   scanf("%d",&m);
   for(int i=0;i<m;i++){
       scanf("%d,%d,%d",&a,&b,&len);
       s.cost=len/100-1;
       s.to=b;
       G[a].push_back(s);
       if(a==0)pq.push(s);
       s.to=a;
       G[b].push_back(s);
       if(b==0)pq.push(s);
   }
   bool spents[101];
   memset(spents,false,sizeof(spents));
   spents[0]=true;
   int count=1,ans=0;
   while(pq.empty()==false){
       s=pq.top();
       pq.pop();
       if(spents[s.to]==true)continue;
       spents[s.to]=true;
       count++;
       ans+=s.cost;
       if(count==n)break;
       for(int i=0;i<G[s.to].size();i++){
           s1=G[s.to][i];
           if(spents[s1.to]==true)continue;
           pq.push(s1);
       }
   }
    printf("%d\n",ans);
}

 
int main(){
   int n;
   while(scanf("%d",&n)!=EOF){
       if(n==0)break;
       calc(n);
    }
}

問73　Surface Area of Quadrangular Pyramid

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0073
底が正方形の四角垂の表面積を求めよという問題。

解法
(ｈ*x)/２の三角形を射影して引き延ばすと側面の三角形の計算式が出てくるって話。

#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("%.7lf\n",x*sqrt(x*x+4*h*h)+x*x);
	}
}

問74　Videotape

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0074
ビデオテープの残り時間を表示する問題。
秒に直して計算するだけです。
3倍録画なんて今どきの若いのに通じるのだろうか？

#include<stdio.h>

int main(){
	int h,m,s,t;
 	while(1){
		scanf("%d %d %d",&h,&m,&s);
		if(h==-1&&m==-1&&s==-1)break;
		t=7200-h*3600-m*60-s;
 		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);
	}
}

問75　BMI

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0075
BMI値を計算して25以上の人の生徒番号だけを出力する問題。
解法
何も工夫するところがありません。

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