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

AOJ再挑戦51~55 - (2014/01/30 (木) 03:02:20) の最新版との変更点

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

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

 *問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];
+ 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);
  	}
  }