「AOJ再挑戦51~55」の編集履歴(バックアップ)一覧はこちら
「AOJ再挑戦51~55」(2014/01/30 (木) 03:15:12) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問51 Differential II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0051
数字の文字列を並べ変えて最大の数と最小の数を作った時その差を計算する問題。
解法
並べ替えて手前と後ろから数字に直すだけです。
#include<stdio.h>
#include<algorithm>
int main(){
int n;
char text[9];
scanf("%d",&n);
while(n--){
int max=0,min=0;
scanf("%s",text);
std::sort(text,text+8);
for(int i=0;i<8;i++) min=min*10+text[i]-'0';
for(int i=7;i>=0;i--)max=max*10+text[i]-'0';
printf("%d\n",max-min);
}
}
*問52 Factorial II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0052
20億!とかの末尾の0の数をこたえる問題。
解法
10^nの素因数は2と5で5の数で5のほうが少ないです。
5,5^2、5^3、、、が何個できるかを集計すれば答えが出ます。
#include<stdio.h>
#include<iostream>
int main(){
long long int n;
while(std::cin>>n){
if(n==0)break;
long long int ans=0,fivePow=5,n1=n;
while(n1>=fivePow){
ans+=n1/fivePow;
fivePow*=5;
}
std::cout<<ans<<"\n";
}
}
*問53 Sum of Prime Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0053
下からn個めまでの素数を足したものをこたえる問題。
解法
篩で求めて下から集計してテーブル化するだけです。
#include<stdio.h>
#include<vector>
#include<string.h>
const int MAX=105000;
bool isPrime[MAX];
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 sum=0;
std::vector<int> memo;
memo.push_back(0);
for(int i=2;i<MAX&&memo.size()<=10000;i++){
if(isPrime[i]){
sum+=i;
memo.push_back(sum);
}
}
int n;
while(scanf("%d",&n)!=EOF){
if(n==0)break;
printf("%d\n",memo[n]);
}
}
*問54 Sum of Nth decimal places
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0054
a/bの小数点1~n桁目までを各桁ごとに足した和をこたえる問題。
解法
小学生の筆算で十分です。
#include<stdio.h>
int main(){
int a,b,n;
while(scanf("%d %d %d",&a,&b,&n)!=EOF){
a=a%b;
int ans=0;
n++;
while(n--){
ans+=(a/b)%10;
a=(a%b)*10;
}
printf("%d\n",ans);
}
}
*問55 Sequence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0055
a a*2 a*2/3 a*2/3*2 a*2/3*2/3
a(1+2+2/3+4/3+4/9+,,,
とすれば一発で出るけれど式変形がめんどくさいのでそのまま求めた。
こういうのめんどくさがるのはよいことではないよな。
#include<stdio.h>
int main(){
double as[10];
while(scanf("%lf",&as[0])!=EOF){
double sum=as[0];
for(int i=1;i<=9;i++){
as[i]=as[i-1]*(i%2?2.0 : 1/3.0);
sum+=as[i];
}
printf("%.9lf\n",sum);
}
}
*問51 Differential II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0051
数字の文字列を並べ変えて最大の数と最小の数を作った時その差を計算する問題。
解法
並べ替えて手前と後ろから数字に直すだけです。
#include<stdio.h>
#include<algorithm>
int main(){
int n;
char text[9];
scanf("%d",&n);
while(n--){
int max=0,min=0;
scanf("%s",text);
std::sort(text,text+8);
for(int i=0;i<8;i++) min=min*10+text[i]-'0';
for(int i=7;i>=0;i--)max=max*10+text[i]-'0';
printf("%d\n",max-min);
}
}
*問52 Factorial II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0052
20億!とかの末尾の0の数をこたえる問題。
解法
10^nの素因数は2と5で5の数で5のほうが少ないです。
5,5^2、5^3、、、が何個できるかを集計すれば答えが出ます。
#include<stdio.h>
#include<iostream>
int main(){
long long int n;
while(std::cin>>n){
if(n==0)break;
long long int ans=0,fivePow=5,n1=n;
while(n1>=fivePow){
ans+=n1/fivePow;
fivePow*=5;
}
std::cout<<ans<<"\n";
}
}
*問53 Sum of Prime Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0053
下からn個めまでの素数を足したものをこたえる問題。
解法
篩で求めて下から集計してテーブル化するだけです。
#include<stdio.h>
#include<vector>
#include<string.h>
const int MAX=105000;
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 sum=0;
std::vector<int> memo;
memo.push_back(0);
for(int i=2;i<MAX&&memo.size()<=10000;i++){
if(isPrime[i]){
sum+=i;
memo.push_back(sum);
}
}
int n;
while(scanf("%d",&n)!=EOF){
if(n==0)break;
printf("%d\n",memo[n]);
}
}
*問54 Sum of Nth decimal places
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0054
a/bの小数点1~n桁目までを各桁ごとに足した和をこたえる問題。
解法
小学生の筆算で十分です。
#include<stdio.h>
int main(){
int a,b,n;
while(scanf("%d %d %d",&a,&b,&n)!=EOF){
a=a%b;
int ans=0;
n++;
while(n--){
ans+=(a/b)%10;
a=(a%b)*10;
}
printf("%d\n",ans);
}
}
*問55 Sequence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0055
a a*2 a*2/3 a*2/3*2 a*2/3*2/3
a(1+2+2/3+4/3+4/9+,,,
とすれば一発で出るけれど式変形がめんどくさいのでそのまま求めた。
こういうのめんどくさがるのはよいことではないよな。
#include<stdio.h>
int main(){
double as[10];
while(scanf("%lf",&as[0])!=EOF){
double sum=as[0];
for(int i=1;i<=9;i++){
as[i]=as[i-1]*(i%2?2.0 : 1/3.0);
sum+=as[i];
}
printf("%.9lf\n",sum);
}
}