AOJ51～60 - c21coterie @ ウィキ

0051　Differential II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0051
8 個の 0 から 9 までの数字を入力したとき、その 8 個の数字を並べ替えてできる、最大の整数と最小の整数の差を出力して終了するプログラムを作成してください。
数字を文字列とみてソートして手前と後ろから合計して差分をとるだけで計算できます。

#include <stdio.h>
#include <algorithm>
int main(){
int max,min,n,ten;
char s[9];
scanf("%d",&n);
for(int i=0;i<n;i++){
	scanf("%s",s);
	std::sort(s,s+8);
	ten=1;
	max=min=0;
	for(int i=0;i<8;i++){
		min+=ten*(s[7-i]-'0');
		max+=ten*(s[i]-'0');
		ten*=10;
	}
	printf("%d\n",max-min);
}

}

---

0052　Factorial II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0052
n!の数字の末尾に0が何個並ぶかを求める問題です。
解法
自分で解法を思いつかなかったので、解説サイトを見て解きました。
解法は原理が分かれば単純、自力で思いつけるかは微妙な問題だと思いますので検索してみることをお勧めします。

#include <stdio.h>
//http://d.hatena.ne.jp/nanikaka/20110727/1311783975#cを参考に原理を理解してリンク先をマルコピ
int main(){
int n,sum;
scanf("%d",&n);
while(n!=0){
	sum=0;
	while(n>4){
		sum+=n/5;
		n/=5;
	}
	printf("%d\n",sum);
	scanf("%d",&n);
}

}

---

0053　Sum of Prime Numbers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0053
素数を小さい方から並べた時i番目までの素数を
素数をエラトステネスの篩で求め、素数を下から足しこんで配列sumsにメモするだけです。

#include <stdio.h>
int sums[10100];
void setSo(){
int so[105000]={0},p=2;
sums[1]=2;
for(int i=3;i<105000;i+=2){
	if(so[i]!=0) continue;
	sums[p]=sums[p-1]+i;
	p++;
	for(int j=i*3;j<105000;j+=i*2){
		so[j]=1;
	}
}
}
int main(){
setSo();
int n;
scanf("%d",&n);
while(n!=0){
	printf("%d\n",sums[n]);
	scanf("%d",&n);
}

}

---

0054　Sum of Nth decimal places

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0054
a/bの少数第一ケタ～第ｎ桁目までの各々の桁の和を求めよという問題。

解法
コードのa*=10;a/b%10がポイントです。
これによりa/ｂの小数点1ケタ目が手に入ります。
後は小学校の筆算と同じ原理です。

#include <stdio.h>
int main(){
int a,b,n,sum;
while(scanf("%d %d %d",&a,&b,&n)!=EOF){
	sum=0;
	a*=10;
	while(n-->0){
		sum+=(a/b)%10;
		a%=b;
		a*=10;
	}
	printf("%d\n",sum);
}

}

---

0055　Sequence

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0055
ある生成規則で生成される数列があるのでその数列の10個目までの計を求めよという問題。
解法
10個目までと計算量が小さいので素朴に解きました。
s(n)を求める公式くらいはあるかもしれません。

#include <stdio.h>
int main(){
double a,sum;
while(scanf("%lf",&a)!=EOF){
	sum=0;
	for(int i=0;i<10;i++){
		sum+=a;
		a=i%2==1?a/3:a*2;
	}
	printf("%.8lf\n",sum);
}

}

---

0056　Goldbach's Conjecture

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0056
4以上の偶数は2つの素数の和で表すことができる。
偶数ｎが与えられるので、何通りの2つの素数の組として表現できるか答えよ。

解法
n=i+(n-i)とし、i,n-i両方が素数ならカウントしていくだけです。
小手先の高速化のために偶数の場合を無視するコードを導入しています。

#include<stdio.h>
int so[50002]={0};
void setSo(){
for(int i=3;i<50001;i+=2){
	if(so[i]!=0) continue;
	for(int j=i*3;j<50001;j+=i*2){
		so[j]=1;
	}
}
}
int main(){
setSo();
int n,sum;
scanf("%d",&n);
while(n!=0){
	sum=0;
	if((n-3)%2==1){
		for(int i=3;i<n/2+1;i+=2){
			if((n-i)<3) break;
			if((so[n-i]|so[i])<1) sum++;
		}
	}
	if((so[n-2]==0 && (n-2)%2==1) || n==4) sum++;
	printf("%d\n",sum);
	scanf("%d",&n);
}

}

---

0057　The Number of Area

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0057
ｎ本の直線で平面を区切る時、平面を何個に分割できるかという問題。
解法
中学校で習った公式をそのまま適用するだけです。
証明はグラフ理論で片が付きます。

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

---

0058　Orthogonal

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0058
直線ＡＢ、ＣＤに関する座標が与えられるので２つが直交するならＹＥＳ、でないならＮＯと出力する問題。
解法
二つの直線が直交するならなす角θはcos(θ)=0を満たすので内積を計算するだけです。

#include<stdio.h>
int main(){
double xs[4],ys[4];
while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2],&xs[3],&ys[3])!=EOF){
	printf("%s\n",(xs[1]-xs[0])*(xs[3]-xs[2])+(ys[1]-ys[0])*(ys[3]-ys[2])==0.0?"YES":"NO");
}

}

---

0059　Intersection of Rectangles

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0059
２つの四角形の座標が与えられるので、重なっているならＹＥＳ重なってないならＮＯと出力する問題。
解法
四角形の当たり判定の公式を適用するだけなので調べてみましょう。
これは最初、自分で解いた時は5倍くらいある長ったらしいコードでした。
当たり判定について調べて書きなおしたのが下記コードとなります。

#include<stdio.h>
int main(){
double xs[4],ys[4];
while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2],&xs[3],&ys[3])!=EOF){
	printf("%s\n",(xs[0]<=xs[3] && ys[0]<=ys[3] && xs[2]<=xs[1]&& ys[2]<=ys[1])?"YES":"NO");
}
}

---

0060 Card Game

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0060
ブラックジャックで自分のカード2枚と相手のカード一枚が見えている。
カード情報より次のカードを引くべきか引かないべきかを答える問題。
解法
普通に使ってないカードを一つずつ調べて２０を超えない場合が何個あるか調べて数えるだけです。
引くカードは7通りしかないので4回以上20以下ならカードを引くと判断。

#include<stdio.h>
int main(){
int c1,c2,c3,m[11],sum;
while(scanf("%d %d %d",&c1,&c2,&c3)!=EOF){
	for(int i=1;i<11;i++) m[i]=0;
	m[c1]=m[c2]=m[c3]=1;
	sum=0;
	for(int i=1;i<11;i++){
		if(m[i]!=1 && c1+c2+i<=20){
			sum++;
		}
	}
	printf("%s\n",sum>3?"YES":"NO");
}
}