「AOJ再挑戦71～75」の編集履歴（バックアップ）一覧はこちら

「AOJ再挑戦71～75」(2014/02/02 (日) 16:19:12) の最新版変更点

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

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

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

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