オイラープロジェクト91～100 の編集履歴一覧 - c21coterie @ ウィキ

オイラープロジェクト91～100 - (2012/09/09 (日) 11:59:31) の編集履歴(バックアップ)

問い91

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

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

#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

各桁の２乗を足し合わせた数を求め、それを繰りかすと必ず1か89に到達する。
１０００万以下で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は素数でありこれの下１０ケタを答えよという問題。
Ｌｉｓｐは苦手だけどＬｉｓｐでなかったらこんなに簡潔には書けない気もする。
Ｌｉｓｐ様様って感じ（俺がヘボいだけかな）

(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)

問い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)という関係を見つけたので後は式変形したら２次方程式を介した漸化式となりました。
とりあえず見つけただけで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";
}
}

c21coterie @ ウィキ