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

オイラープロジェクト121~130 - (2012/09/10 (月) 18:22:33) の1つ前との変更点

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

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

 *問い121
 袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている. ある賭けゲームにおいて, プレイヤーは円盤を 1 枚ランダムに取り出しその色を記録する. 各ターンの終わりに円盤は袋に戻され, 追加の赤い円盤 1 枚が袋に足され, そして次の円盤がランダムに取り出される.
 プレイヤーはゲームをプレイするのに 1 ポンドを支払い, ゲーム終了時に青い円盤を赤い円盤より多く取り出していれば勝利する.
 ゲームが 4 ターンプレイされたとすると, プレイヤーが勝利する確率はちょうど 11/120 となる. したがって, 胴元が赤字の見込みになるまでにこのゲームで勝ちに対して割り当てるべき賞金の最大は 10 ポンドとなるであろう. 支払いはすべてポンドの整数倍であり, またゲームをプレイするのに支払われたもともとの 1 ポンドを含んでいるため, 与えられた例では実際にはプレイヤーは 9 ポンドを獲得することに注意しよう.
 15 ターンがプレイされるゲーム 1 回に割り当てられるべき賞金の最大を求めよ.
 解法
 組み合わせ数が少ないのでLispの分数計算で全探索します。
 
  (defun saiki (p deep get)
    (if (= deep 15)
        (if (< (/ deep 2) get) p 0)
      (+ (saiki (* p (/ 1 (+ deep 2))) (+ deep 1) (+ get 1))
         (saiki (* p (/ (+ deep 1) (+ deep 2))) (+ deep 1) get))))
  saiki
  (let ((a (saiki 1 0 0)) (b 0) (c 0))
    (setq b (numerator a)
  	c (denominator a))
    (floor (/ c b)))
 
 
 
 *問い123
 pn を n 番目の素数とする. (p1 = 2, p2 = 3, ...) r を (pn - 1)n + (pn + 1)n を pn2 で割った余りとする.
 例えば, n = 3 のとき, p3 = 5 であり, 43 + 63 = 280 ≡ 5 mod 25.
 余り r が 109 より大きくなる n の最小値は 7037 である.
 余り r が 1010 より大きくなる最初の n を求めよ.
 
 モード演算は分けて個別に計算しても全部合わせて計算しても答えが変わらないということを利用してステップ単位で解きます。
 
 高速化しようと考え
 n^23=n^16*n^4*n^2*n^1のように累乗が2^累乗の指数に分解出来る性質を利用して解こうとしたらint64で溢れるので上手くいきません。
 Lispなら高速化は簡単ですがC++では多倍張整数を用意しないと無理かもしれません。
 
 
 
 
  #include<stdio.h>
  #include<vector>
  #include<iostream>
  const int up=1000000;
  std::vector<__int64> sosuu; 
  bool so[up];
  void setSo(){
 	int i2;
 	memset(so,true,sizeof(so));
 	sosuu.push_back(2);
 	for(int i=3;i<=up;i+=2){
 		if(so[i]==false)continue;
 		sosuu.push_back(i);
 		i2=i*2;
 		for(int j=i*3;j<up;j+=i2){
 			so[j]=false;
 		}
 	}
  }
  int main(){
 	setSo();
 	__int64 p,pd,pu,p2,calcD,calcU,ten=1;
 	for(int i=0;i<10;i++){
 		ten*=10;
 	}
 	for(int i=0;i<sosuu.size();i++){
 		p=sosuu[i];
 		p2=p*p;
 		calcD=pd=p-1;
 		calcU=pu=p+1;
 		for(int n=0;n<i;n++){
 			calcD=(calcD*pd)%p2;
 			calcU=(calcU*pu)%p2;
 		}
 		//std::cout<<(calcD+calcU)%p2<<"\n";
 		if((calcU+calcD)%p2>ten){
 			std::cout<<i+1;
 			break;
 		}
 	}
 	std::cout<<"?";
+ }
+
+
+
+
+
+
+*問い124
+n の"根基"(radical)は、rad(n) で表し、n の素因数の積を意味する。 例えば 504 = 23 × 32 × 7 であるから、 rad(504) = 2 × 3 × 7 = 42 である。
+1 ≤ n ≤ 10 に対して rad(n) を計算し、rad(n) を対象にソートし、 rad(n) が同じ場合は n を対象にソートすると以下のようになる。
+未ソート	       	ソート済み
+n	rad(n)		n	rad(n)	k
+1	1		1	1	1
+2	2		2	2	2
+3	3		4	2	3
+4	2		8	2	4
+5	5		3	3	5
+6	6		9	3	6
+7	7		5	5	7
+8	2		6	6	8
+9	3		7	7	9
+10	10		10	10	10
+E(k) をソートした表の n の列の k 番目の要素とする。 例えば、 E(4) = 8, E(6) = 9 である。
+rad(n) を 1 ≤ n ≤ 100000 でソートした場合、 E(10000) を求めよ。
+
+普通に構造体を定義して優先順位付きキューに放り込むだけです。
+この時10000個目を超えた分はいらないので無視します。
+
+
+ #include<stdio.h>
+ #include<queue>
+ struct S{
+	int n,rad;
+	bool operator<(const S& s)const{
+		if(rad!=s.rad)return rad<s.rad;
+		return n<s.n;
+	}
+	void set(int n1){
+		n=n1;
+		rad=1;
+		for(int i=2;i*i<=n;i++){
+			if(n1%i==0){
+				rad*=i;
+				while(n1%i==0)n1/=i;
+			}
+		}
+		rad*=n1;
+	}
+ };
+ int main(){
+	int count=0;
+	std::priority_queue<S> pQ;
+	S s;
+	for(int i=1;i<= 100000;i++){
+		s.set(i);
+		pQ.push(s);
+		count++;
+		if(count>10000)pQ.pop();
+	}
+	s=pQ.top();
+	printf("%d %d\n",s.n,s.rad);
  }