「AOJ再挑戦56~60」の編集履歴(バックアップ)一覧に戻る

AOJ再挑戦56~60 - (2014/01/30 (木) 03:56:57) の最新版との変更点

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

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

-*Goldbach's Conjecture
+*問56 Goldbach's Conjecture
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0056
 ゴールドバッハ予想に関する問題。
 解法
 篩にかけてあとはテーブル化して数えるだけです。
 
 
  #include<stdio.h>
  #include<string.h>
  const int MAX=60000;
  bool isPrime[MAX+1];
  
  void calc(){
  	memset(isPrime,true,sizeof(isPrime));
  	isPrime[0]=isPrime[1]=false;
  	for(int i=2;i*i<=MAX;i+=(1+(i&1))){
  		if(isPrime[i]==false)continue;
  		int add=i%2==0?i:i*2;
  		for(int j=(i%2==0?i*2:i*3);j<=MAX;j+=add){
   			isPrime[j]=false;
   		}
  	}
  }
  
  int main(){
  	calc();
  	int n;
   	while(scanf("%d",&n)!=EOF){
  		int p1,p2;
  		for(p1=n-1;isPrime[p1]==false;p1--);
   		for(p2=n+1;isPrime[p2]==false;p2++);
   		printf("%d %d\n",p1,p2);
  	}
  }
 
 
 
 *問57 The Number of Area
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0057
 平面をn本の直線で分割した時、最大の分割数をこたえる問題。
 n本ひかれたときにn+1本目はn本全部と交差する。
 これはn+1個の平面を2つに分割する事と同じだからn+1個分割が増える。
 
 
  #include<stdio.h>
  
  int main(){
  	int n;
   	while(scanf("%d",&n)!=EOF){
  		printf("%d\n",1+(n*(n+1))/2);
  	}
  }
 
 
 
 *問58 Orthogonal
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0058
 2直線が直交しているかを判定する問題。
 
 内積で解けます。
 計算誤差が微妙に出るのでその数値設定だけの問題です。
 
  #include<stdio.h>
  #include <math.h>
  
  int main(){
  	double xa,xb,xc,xd;
  	double ya,yb,yc,yd;
  	while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf",
  			&xa,&ya,&xb,&yb,&xc,&yc,&xd,&yd)!=EOF){
  		double dx1,dx2,dy1,dy2,naiseki;
   		dx1=xb-xa;
  		dy1=yb-ya;
  		dx2=xd-xc;
  		dy2=yd-yc;
   		naiseki=fabs(dx1*dx2+dy1*dy2);
  		printf("%s\n",naiseki<0.0000000001?"YES":"NO");
  	}
  }
 
 
 
 
 *問59Intersection of Rectangles
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0059
 2つの矩形領域の重なり判定をする問題。
 集合論的に考えたら、二つ目の矩形の右端が1つ目の矩形の左端より右にないと重ならないし。
 反対でも上下でも同様。
 これだけ。
 
  #include<stdio.h>
  int main(){
  	double xa1,xa2,xb1,xb2;
  	double ya1,ya2,yb1,yb2;
  	while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf",
  			&xa1,&ya1,&xa2,&ya2,&xb1,&yb1,&xb2,&yb2)!=EOF){
  		bool hit=true;
  		if( xb2<xa1 || xa2<xb1 || yb2<ya1 || ya2<yb1)hit=false;
   		printf("%s\n",hit?"YES":"NO");
+ 	}
+ }
+
+
+
+*Card Game
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0060
+2人プレイのカードゲームを題材にした問題。
+解法
+問題文がややこしいがようは自分が後一枚引いて3枚のカードの合計が20以下になる確率だけもとめればよい。
+50%以上なので、一枚引いて勝てる場合が4回以上なら勝ちである。
+
+ #include<stdio.h>
+  
+ int main(){
+  	int c1,c2,c3;
+ 	while(scanf("%d %d %d",&c1,&c2,&c3)!=EOF){
+ 		bool spetns[11];
+ 		int okCount=0;
+ 		for(int i=1;i<=9;i++){
+ 			if(i!=c1&&i!=c2&&i!=c3){
+ 				if(c1+c2+i<=20)okCount++;
+ 			}
+  		}
+ 		printf("%s\n",okCount>3?"YES":"NO");
  	}
  }