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

オイラープロジェクト41~50 - (2012/08/27 (月) 15:08:48) の編集履歴(バックアップ)


問い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

三角数Pi,Pj。
Pi+PjとD=|Pi-Pj|の両方が三角数になる時の最小の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;
}