「AOJ再挑戦31～35」の編集履歴（バックアップ）一覧に戻る

AOJ再挑戦31～35 - (2014/01/28 (火) 09:33:32) のソース

*問31　Weight
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0031&lang=jp
天秤で重さを図るときの問題

解法
２＾ｎで考えたらｎのビットがたってるものだけ出力。
あとはｎ/２で割ったあとｎが0でないならまだのせるものがあるのでスペースを出力。

 
 #include<stdio.h>
 
 int main(){
 	int n;
 	while(scanf("%d",&n)!=EOF){
 		int a=1;
  		while(n!=0){
 			if(n%2==1){
 				printf("%d",a);
 				n/=2;
 				if(n>0)printf(" ");
  			}else{
 				n/=2;
 			}
 			a*=2;
  		}
 		printf("\n");
 	}
 }



*問３２ Plastic Board
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0032
長方形とひし形とそれ以外を判別して数える問題

**解法
長方形なら3平方が成り立ち成り立たないなら、ひし形の可能性しかない。
ひし形なら隣り合う2辺は同じ長さ。
そうでないならひし形でもない。

 #include<stdio.h>  
 int main(){
  	int a,b,c,ans1=0,ans2=0;
 	while(scanf("%d,%d,%d",&a,&b,&c)!=EOF){
 		if(a*a+b*b==c*c){
 			ans1++;
 		}else if(a==b){
  			ans2++;
 		}
 	}	
 	printf("%d\n%d\n",ans1,ans2);
 }


*問３３　Ball
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0033
ボールを左右に分けていく問題。

解法
優先して左に入れる、入らなければ右に入らないか試す。
両方駄目ならどうやっても入らない。
それだけ、計算量は一回のボールセットで10。

 #include<stdio.h> 
 int main(){
 	int n,l,r,b;
 	scanf("%d",&n);
 	while(n--){
  		l=r=0;//左のほうが常に大きくなるようにする入らなければ右
		bool ok=true;
  		for(int i=0;i<10;i++){
 			scanf("%d",&b);
 			if(l<b){
 				l=b;
  			}else if(r<b){
 				r=b;
 			}else{
 				ok=false;
  			}
 		}
 		printf("%s\n",ok?"YES":"NO");
 	}
 }



*問34　Railway Lines
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0034
電車がすれ違う区間をこたえる問題。
解法
両方の電車の相対速度で両電車は違づくのでそれからすれ違うタイムが出てあとはすれ違うポイントを探すだけです。

 #include<stdio.h>
 
 int main(){
 	double Ls[11],L,v1,v2;
  	while(1){
 		Ls[0]=0;
 		if(scanf("%lf,",&Ls[1])==EOF)break;
 		for(int i=2;i<11;i++){
 			scanf("%lf,",&L);
 			Ls[i]=Ls[i-1]+L;
  		}
 		scanf("%lf,%lf",&v1,&v2);
 		double p=v1*Ls[10]/(v1+v2);
 		int ans=0;
 		for(int i=0;i<11;i++){
  			if(p<=Ls[i]){
 				ans=i;
 				break;
 			}
 		}
  		printf("%d\n",ans);
 	}
 }



*問35　　Is it Convex?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0035
凸多角形の判定問題
凸多角形をいいなおせば、頂点で曲がるときかならず右曲りか左曲りに曲がりどちらかが４つ連続すればそれは凸です。
外積で判定するだけです。


 #include<stdio.h>
 
 int main(){
 	double xs[4],ys[4];
 	while(1){
 		if(scanf("%lf,%lf",&xs[0],&ys[0])==EOF)break;
 		for(int i=1;i<4;i++){
  			scanf(",%lf,%lf",&xs[i],&ys[i]);
 		}
 		int count=0;
 		for(int i=0;i<4;i++){
 			int p1=i;
 			int p2=(i+1)%4;
  			int p3=(i+2)%4;
 			double dx2,dy2,dx3,dy3;
 			dx2=xs[p2]-xs[p1];
 			dy2=ys[p2]-ys[p1];
 			dx3=xs[p3]-xs[p1];
  			dy3=ys[p3]-ys[p1];
 			count+=(dx2*dy3-dx3*dy2>0?1:-1);
 		}
  		printf("%s\n",count==4||count==-4?"YES":"NO");
 　	}
 }