「AOJ再挑戦56～60」の編集履歴（バックアップ）一覧はこちら
「AOJ再挑戦56～60」(2014/01/30 (木) 04:14:11) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問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本ひかれたときにｎ+1本目はｎ本全部と交差する。
これはｎ+1個の平面を２つに分割する事と同じだからｎ+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
２直線が直交しているかを判定する問題。
内積で解けます。
計算誤差が微妙に出るのでその数値設定だけの問題です。
#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
２つの矩形領域の重なり判定をする問題。
集合論的に考えたら、二つ目の矩形の右端が１つ目の矩形の左端より右にないと重ならないし。
反対でも上下でも同様。
これだけ。
#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
２人プレイのカードゲームを題材にした問題。
解法
問題文がややこしいがようは自分が後一枚引いて３枚のカードの合計が２０以下になる確率だけもとめればよい。
50％以上なので、一枚引いて勝てる場合が４回以上なら勝ちである。
#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");
}
}
*問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本ひかれたときにｎ+1本目はｎ本全部と交差する。
これはｎ+1個の平面を２つに分割する事と同じだからｎ+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
２直線が直交しているかを判定する問題。
内積で解けます。
計算誤差が微妙に出るのでその数値設定だけの問題です。
#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
２つの矩形領域の重なり判定をする問題。
集合論的に考えたら、二つ目の矩形の右端が１つ目の矩形の左端より右にないと重ならないし。
反対でも上下でも同様。
これだけ。
#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
２人プレイのカードゲームを題材にした問題。
解法
問題文がややこしいがようは自分が後一枚引いて３枚のカードの合計が２０以下になる確率だけもとめればよい。
50％以上なので、一枚引いて勝てる場合が４回以上なら勝ちである。
#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");
}
}
