「AOJ51~60」の編集履歴(バックアップ)一覧はこちら
「AOJ51~60」(2011/10/30 (日) 17:30:28) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*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の少数第一ケタ~第n桁目までの各々の桁の和を求めよという問題。
解法
コードのa*=10;a/b%10がポイントです。
これによりa/bの小数点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つの素数の和で表すことができる。
偶数nが与えられるので、何通りの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
n本の直線で平面を区切る時、平面を何個に分割できるかという問題。
解法
中学校で習った公式をそのまま適用するだけです。
証明はグラフ理論で片が付きます。
#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
直線AB、CDに関する座標が与えられるので2つが直交するならYES、でないならNOと出力する問題。
解法
二つの直線が直交するならなす角θは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
2つの四角形の座標が与えられるので、重なっているならYES重なってないならNOと出力する問題。
解法
四角形の当たり判定の公式を適用するだけなので調べてみましょう。
これは最初、自分で解いた時は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枚と相手のカード一枚が見えている。
カード情報より次のカードを引くべきか引かないべきかを答える問題。
解法
普通に使ってないカードを一つずつ調べて20を超えない場合が何個あるか調べて数えるだけです。
引くカードは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");
}
}
*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の少数第一ケタ~第n桁目までの各々の桁の和を求めよという問題。
解法
コードのa*=10;a/b%10がポイントです。
これによりa/bの小数点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つの素数の和で表すことができる。
偶数nが与えられるので、何通りの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
n本の直線で平面を区切る時、平面を何個に分割できるかという問題。
解法
中学校で習った公式をそのまま適用するだけです。
証明はグラフ理論で片が付きます。
#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
直線AB、CDに関する座標が与えられるので2つが直交するならYES、でないならNOと出力する問題。
解法
二つの直線が直交するならなす角θは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
2つの四角形の座標が与えられるので、重なっているならYES重なってないならNOと出力する問題。
解法
四角形の当たり判定の公式を適用するだけなので調べてみましょう。
これは最初、自分で解いた時は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枚と相手のカード一枚が見えている。
カード情報より次のカードを引くべきか引かないべきかを答える問題。
解法
普通に使ってないカードを一つずつ調べて20を超えない場合が何個あるか調べて数えるだけです。
引くカードは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");
}
}