※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「オイラープロジェクト41~50」の編集履歴(バックアップ)一覧に戻る

オイラープロジェクト41~50 - (2012/08/31 (金) 19:34:11) の編集履歴(バックアップ)


問い41

n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつもつこととする.
#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁Pandigital数であり, かつ素数である. n桁(この問題の定義では9桁以下)Pandigitalな素数の中で最大の数を答えよ.

パンデジタル数を大きい順に順列で生成して後は素数かどうか簡易検査するだけです。



#include<stdio.h>
#include<math.h>
bool perms[10];
int ans=-1;
bool isSosuu(int n){
//素数かどうかの簡易チェック
int m=sqrt(n);
if(n==m*m||n%2==0)return false;//2の倍数かmで割り切れるなら
for(int i=3;i<m;i+=2){
	if(n%i==0)return false;//奇数で割ってみる
}
return true;
}
void saiki(int sum,int deep,int k){
if(deep==k){
	//printf("%d\n",sum);
	if(isSosuu(sum)==true){
		ans=sum;
	}
}else{
	for(int i=k;i>0;i--){
		if(perms[i]==true){
			perms[i]=false;
			saiki(sum*10+i,deep+1,k);
			if(ans!=-1)return ;
			perms[i]=true;
		}
	}
}

}
int main(){
perms[0]=false;
for(int i=9;i>0;i--){
	//桁数i
	for(int j=1;j<=i;j++)perms[j]=true;
	saiki(0,0,i);
	if(ans!=-1)break;
}
printf("%d\n",ans);
}



問い42

三角語と呼ばれる単語がテキストファイルの中にいくつあるか数える問題。
最大値の見極めがつかないので少しメモリをぜいたくに使って後は愚直に一つずつ計算。
まあ計算すればいいわけだけどファイルは中身が見えないブラックなファイルとして扱いたいし、練習問題でコードサイズは膨らましたくないのでこのコードに落ち着いた感じ。




#include <stdio.h>
#include <string.h>
 #include <map>
int main(){
	FILE *fp;
	if((fp=fopen("words.txt","r"))==NULL){
		printf("fileOpenError");
		exit(EXIT_FAILURE);
	}
	char text[102];
	int max=0;
	std::map<int,int> memo;
	while(fscanf(fp,"\"%[^\"]\",",text)>0){
		int sum=0;
		for(int i=0;i<strlen(text);i++){
			sum+=text[i]-'A'+1;
		}
	//printf("(%s %d %d)",text,sum,max);
		if(max<sum)max=sum;
		if(memo.find(sum)!=memo.end()){
			memo[sum]++;
		}else{
			memo[sum]=1;
		}
	}
	fclose(fp);
int t=0,ans=0; 
	for(int i=1;t<=max;i++){
		t=((i+1)*i)/2;
		ans+=memo.find(t)!=memo.end()?memo[t]:0;
	} 
	printf("%d\n",ans);
}



問い44

5角数Pi,Pjについて考える。
Pi+PjとD=|Pi-Pj|の両方が5角数になる時の最小のDを答えよ。
とりあえず最初に見つかった条件を満たす数を投稿したら合格したものの、厳密にはきちんとは解けてない問題。
このコードはもっと大きな数の差分に条件を満たす数がないか続きを調べさせるといつまでも計算が終わらない。




#include<stdio.h>
#include<set>
#include<iostream>
int main(){
__int64 min=-1,num1,num2,i=2,j,ansD,ansUP;
std::set<__int64> memo,next;
std::set<__int64>::reverse_iterator it;
memo.insert(1);
	
while(1){
	num1=(i*(3*i-1))/2;
	j=i-1;
	num2=(j*(3*j-1))/2;
	if(min>-1&&num1-num2>=min)break;
	__int64 k=i+1;
	next.clear();
	while((k*(3*k-1))/2<=num1*2){
		next.insert((k*(3*k-1))/2);
		k++;
	}
	for(it=memo.rbegin();it!=memo.rend();it++){
		if((*it)>num1)continue;
		num2=num1-(*it);
		if(min>-1&&num2>=min)break;
		if((min==-1||min>num2)&&memo.find(num2)!=memo.end()&&next.find(num1+(*it))!=next.end()){
			min=num2;
			ansUP=num1;
			ansD=(*it);
			std::cout<<min<<" "<<ansUP<<" "<<ansD;
			return 0;
		}
	}
	memo.insert(num1);
	i++;
}
}





問い45

三角数∧5角数∧6角数∧40755より大きな最小の数を求めよ。
マージソートの考え方で小さい分を少しずつ増量させればいいです。
意外と大きな数が答えになりました。

#include<stdio.h>
#include<iostream>
int main(){
__int64 n3=286,n5=166,n6=144,p3,p5,p6;
p3=(n3*(n3+1))/2;
p5=(n5*(3*n5-1))/2;
p6=(n6*(2*n6-1));

while(p3!=p5 || p5!=p6 || p3!=p6){
	if(p3<=p5 && p3<=p6){
		n3++;
	}else if(p5<=p3 && p5<=p6){
		n5++;
	}else if(p6<=p3 && p6<=p5){
		n6++;
	}
	p3=(n3*(n3+1))/2;
	p5=(n5*(3*n5-1))/2;
	p6=(n6*(2*n6-1));
	//std::cout<<p3<<" "<<p5<<" "<<p6<<"\n";
}
std::cout<<p3<<" "<<p5<<" "<<p6; 
}






問い48

Σi^i(i=1...1000)の下10ケタを求めよという問題。


int main(){
__int64 ans=0,b,m=10000000000;
for(int i=1;i<1001;i++){
	b=1;
	for(int j=0;j<i;j++){
		b=(b*i)%m;//ここは工夫して計算量を落としてもいいんだけどたった100万回だしまあいいか
	}
	ans=(ans+b)%m;
}
std::cout<<ans;
}