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

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

オイラープロジェクト91~100 - (2012/09/11 (火) 20:29:08) の編集履歴(バックアップ)


問い91

xy平面上の0<=x<=50&&0<=y<=50の範囲で原点と整数座標2点で三角形を作るとき直角三角形はいくつ作ることが出来るか。

計算量の少ない解法を記述するのがめんどくさかったので手抜きでクリア。
全探索しても6250万通りと組み合わせ数が少ないので一瞬で計算が終わります。
多分この問題が出題された当時だと1分ルールは切れないのでしょうが今のパソコンでは一瞬ですね。


#include<stdio.h>
#include<algorithm>
int main(){
int a[3];
int size=50,ans=0;
for(int x1=0;x1<=size;x1++){
	for(int y1=0;y1<=size;y1++){
		if(x1==0&&y1==0)continue;
		for(int x2=0;x2<=size;x2++){
			for(int y2=0;y2<=size;y2++){
				if((x2==0&&y2==0)||(x2==x1&&y2==y1))continue;
				a[0]=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
				a[1]=x1*x1+y1*y1;
				a[2]=x2*x2+y2*y2;
				std::sort(a,a+3);
				if(a[0]+a[1]==a[2]){
					ans++;
				}
			}
		}
	}
}
printf("%d",ans/2);
}



問い92

各桁の2乗を足し合わせた数を求め、それを繰りかすと必ず1か89に到達する。
1000万以下で89に到達する数の個数を求めよ。


#include<stdio.h>
int memo[1000]={0};
int saiki(int n){
if(n==1||n==89){
	return n;
}
if(n<1000&&memo[n]!=0)return memo[n];
int next=0,m=n;
while(m!=0){
	next+=(m%10)*(m%10);
	m/=10;
}
m=saiki(next);
if(n<1000)memo[n]=m;
return m;
}
int main(){
int ans=0;
for(int i=1;i<10000000;i++){
	ans+=(saiki(i)==89);
}
printf("%d",ans);
}




問い95

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2095
100万以下の要素で構成された友愛鎖のうち一番長い鎖の一番小さい値を求めよ。
メモ化で高速化のつもりが妙に時間がかかった。
もう少し早いつもりだったんだけどな。


#include<stdio.h>
#include<math.h>
#include<iostream>
const int up=1000000;
int memo[up+2]={0};
__int64 wa(int n){
__int64 up=sqrt(n),c1,t,re=1,s=n;
for(int i=2;i<=up;i++){
	c1=1;
	t=1;
	while(n%i==0){
		n/=i;
		t*=i;
		c1+=t;
	}
	re*=c1;
}
if(n!=1){
	re*=(n+1);
}
return re-s;
}
int saiki(__int64 n,int s,int deep){
if(n>=up)return 0;//100万を超えてしまった
if(s==n&&deep>0)return deep;//輪になった
if(memo[(int)n]!=0)return 0;//他の輪に外から入ってしまった
memo[(int)n]=1;//とりあえず使用済みにしておく
int re=saiki(wa(n),s,deep+1);
memo[(int)n]=re;//正式にループの長さが決まった
return re;
}
int main(){
for(int i=2;i<up;i++){
	if(memo[i]==0){
		saiki(i,i,0);
	}
}
int ans,loopSize=0;
for(int i=0;i<up;i++){
	if(memo[i]>loopSize){
		ans=i;
		loopSize=memo[i];
	}
}
printf("%d %d\n",ans,loopSize);
}




問い97

28433×2^7830457+1は素数でありこれの下10ケタを答えよという問題。
Lispは苦手だけどLispでなかったらこんなに簡潔には書けない気もする。
Lisp様様って感じ(俺がヘボいだけかな)



(defvar mask 10000000000)
mask
(setq mask 10000000000)
10000000000
(defun saiki (n m all)
  (if (< 0 m)
      (if (= (mod m 2) 1) 
	  (saiki (mod (* n n) mask) (floor (/ m 2)) (mod (* all n) mask))
	(saiki (mod (* n n) mask) (floor (/ m 2)) all))
    all))
saiki
(mod (+ (* (saiki 2 7830457 1)  28433) 1) mask)




問い98

CARE という単語の各文字をそれぞれ 1, 2, 9, 6 に置き換えることによって, 平方数 1296 = 362 ができる. 注目すべきことに, 同じ数字の置換をつかうことにより, アナグラムの RACE も平方数 9216 = 962 をつくる. CARE (と RACE) を平方アナグラム単語対と呼ぼう. 先頭のゼロは許されず, 異なる文字が同じ数字をもつこともないとする.
約 2,000 個の一般的な英単語を含む 16K のテキストファイルwords.txt (右クリックして "名前をつけてリンク先を保存") を用いて, 平方アナグラム単語対をすべて求めよ (回文となる単語はそれ自身のアナグラムとはみなさない).
そのような対のメンバーから作られる最大の平方数は何か?
注: 作られるアナグラムは, すべて与えられたテキストファイルに含まれている


ひたすらめんどくさいだけの問題。
面倒だったので邪道なテクニックを使ってアセプト。
文字列をなるたけ手前から直接数字列に変換して(¥0を避けるために、+1大きく変換)して最後に数字に直して平方数かチェック。
これを再帰関数を使って実装した。
それでもコードサイズが膨らんだ、、、
この問題の正答率が低いのはとにかくめんどくさいからに違いない。


#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#include<map>
#include<string>
#include<vector>
#include<iostream>
//何だかめんどくさい問題なので邪道な手口を使ってコードを短縮する
//実務では100%禁じ手だろうな
struct S{
int cs[27];
bool operator<(const S& s)const{
	for(int i=0;i<27;i++){
		if(cs[i]!=s.cs[i])return cs[i]<s.cs[i];
	}
	return false;
}
};
__int64 ans=0;
int spents[11]={0};
__int64 stringToNum(std::string str){
if(str[0]==1)return -1;//小さい数字なら何でもいい
__int64 re=0;
for(int i=0;str[i]!='\0';i++){
	re=re*10+(str[i]-1);
}
return re;
}
void saiki(int deep,std::string w1,std::string w2){
if(deep==w1.size()){
	__int64 k1,k2,n1=stringToNum(w1),n2=stringToNum(w2);
	if(n1==1||n2==1)return;
	k1=sqrt(n1);
	k2=sqrt(n2);
	if(k1*k1==n1&&k2*k2==n2){
		if(ans<n1)ans=n1;
		if(ans<n2)ans=n2;
		//std::cout<<"("<<n1<<" "<<n2<<")";
	}
}else{
	//この文字は数字に変換済み
	if(w1[deep]<11){
		saiki(deep+1,w1,w2);
		return ;
	}		
	__int64 next1,next2;
	std::string nextW1,nextW2;
	char c;
	for(int i=1;i<11;i++){
		//\0の取り扱いがめんどくさいので数字を1大きくして文字列を数字に変換する
		//実務でないからこそだな
		if(i==1&&deep==0)continue;
		if(spents[i]==0){
			spents[i]=1;
			nextW1=w1;
			nextW2=w2;
			c=w1[deep];
			for(int j=0;j<w1[j]!='\0';j++){
				if(w1[j]==c){
					nextW1[j]=i;
				}
				if(w2[j]==c){
					nextW2[j]=i;
				}
			}
			saiki(deep+1,nextW1,nextW2);
			spents[i]=0;
		}
	}
}
}
int main(){
char front[10],text[20],c;
FILE *fp;
if ((fp = fopen("euler98Data.txt", "r")) == NULL) {
	printf("file open error!!\n");
	exit(EXIT_FAILURE);	/* (3)エラーの場合は通常、異常終了する */
}
S s;
std::vector<std::string> vec;
std::map<S,std::vector<std::string> > memo;
std::map<S,std::vector<std::string> >::iterator it;
std::string str1,str2;
	
while(fscanf(fp,"%[^\"]\"%[^\"]\"",front,text)!=EOF){
	memset(s.cs,0,sizeof(s.cs));
	for(int i=0;text[i]!='\0';i++){
		s.cs[text[i]-'A']++;
	}
	if(memo.find(s)==memo.end()){
		vec.push_back(text);
		memo[s]=vec;
		vec.pop_back();
	}else{
		memo[s].push_back(text);
	}
	if(fscanf(fp,"%c",&c)==EOF)break;
}
fclose(fp);
printf("\nallRead\n");
for(it=memo.begin();it!=memo.end();it++){
	//テキストを解析した結果対になるアナグラムが3つ以上はないことが判明
	if((*it).second.size()>1){
		str1=(*it).second[0];
		str2=(*it).second[1];
		std::cout<<"<"<<str1<<" "<<str2<<">\n";
		saiki(0,str1,str2);
	}
}
std::cout<<ans<<"\n";
}



問い99

数万^数万乗形式の大きな数が1000行与えられるので一番大きな数字の書かれた行を探せという問題。
対数を使って計算すれば楽勝。
楽勝なんだけど、このコードで合格出来たけど一応1だけ数字が違うのきたら大小関係が判別できないはずだけどこれで合格でいいのかな?


#include<stdio.h>
#include<math.h>
int main(){
double a,b,c,myMax=0;
int ansNo;
for(int i=0;i<1000;i++){
	scanf("%lf,%lf",&a,&b);
	c=log(a)*b;
	printf("( %lf %lf)\n",log(a),b);
	if(c>myMax){
		myMax=c;
		ansNo=i+1;
	}
}
printf("%d\n",ansNo);
} 



問い100

箱の中に15個の青い円盤と6個の赤い円盤からなる21個の色のついた円盤が入っていて、無作為に2つ取り出すとき、青い円盤2つを取り出す確率P(BB)は
P(BB) = (15/21) × (14/20) = 1/2
であることがわかる。
無作為に2つ取り出すとき、青い円盤2つを取り出す確率がちょうど1/2となるような次の組み合わせは、箱が85個の青い円盤と35個の赤い円盤からなるときである。
箱の中の円盤の合計が1012 = 1,000,000,000,000を超えるような最初の組み合わせを考える。箱の中の青い円盤の数を求めよ

値が小さな場合について全探索で求め、出てきた数列を眺めた結果。
(A/N)*(A-1)/(N-1)=1/2に
C(i+1)=(Ni+Ai)-1
N(i+1)-A(i+1)=C(i+1)という関係を見つけたので後は式変形したら2次方程式を介した漸化式となりました。
とりあえず見つけただけでCiが何故成立するか分かってません。



#include<stdio.h>
#include<math.h>
#include<iostream>
#include <iomanip>
int main(){
double a=15,n=21,n2,a2,c;
std::cout.precision(4);
std::cout.setf(std::ios::fixed);
while(n<1000000000000.0){
	c=a+n-1;
	n2=(1+4*c+sqrt(8*c*c+1))/2.0;
	a=n2-c;
	n=n2;
	std::cout<<a<<"/"<<n<<"\n";
}
}