問題一覧 > 教育的問題

No.2122 黄金比で擬似乱数生成

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : 👑 p-adicp-adic / テスター : googol_S0googol_S0 shino16shino16
1 ProblemId : 8309 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-12 10:21:53

問題文

入力に文字 $0$ ~ $9$ のみからなる長さ $4$ の文字列 $S$ と非負整数 $M,L$ が与えられます。

 

非負整数 $m$ に対し、文字 $0$ ~ $9$ のみからなる長さ $4$ の文字列 $s$ に対する以下の一連の操作をここでは $m$ シャッフルと呼ぶことにします:

  1. $s$ が表す非負整数を $n$ と置く。
  2. $2$ 次方程式 $x^2 - nx - 1 = 0$ の $2$ 実数解のうち大きい方を $\alpha$ と置き、判別式を $D$ と置く。
  3. $s$ を $\frac{\alpha^m}{\sqrt{D}}$ の整数部分の下 $4$ 桁で置き換える。(ただし $\frac{\alpha^m}{\sqrt{D}}$ の整数部分が $3$ 桁以下しかない場合は先頭に $0$ を追加して $4$ 桁に揃える)

 

$S$ に $M$ シャッフルを $L$ 回施した結果得られる文字列を求めてください。

入力

入力は次の形式で標準入力から与えられます:

$S$
$M$
$L$

制約

入力 $S,M,L $は以下の制約を満たします:

  • $S$ は文字 $0$ ~ $9$ のみからなる長さ $4$ の文字列
  • $M$ は $10^{18}$ 以下の非負整数
  • $L$ は $10^{18}$ 以下の非負整数

出力

$S$ に $M$ シャッフルを $L$ 回施した結果得られる文字列を $1$ 行に出力してください。

最後に改行してください。

サンプル

サンプル1
入力
0001
4
1
出力
0003

$S = 0001$ が表す非負整数 $n$ は $1$ となります。$2$ 次方程式

$\displaystyle x^2 - n x - 1 = 0 $

は $2$ 実数解が $\frac{1 \pm \sqrt{5}}{2}$ でそのうちの大きい方 $\alpha$ は黄金比を表す値 $\frac{1 + \sqrt{5}}{2} = 1.6 \cdots$ となり、判別式 $D$ が $n^2 + 4 = 5$ なので $\sqrt{D}$ は $\sqrt{5} = 2.2 \cdots$ となります。

$\frac{\alpha^M}{\sqrt{D}} = \frac{\alpha^4}{\sqrt{D}} = 3.0 \cdots$ であるので、その整数部分の下 $4$ 桁は $0003$ となります。

すなわち $S = 0001$ に $M$ シャッフルを施すと$0003$となり、今回は $L = 1$なのでこれで操作が終了します。

サンプル2
入力
0001
2
10
出力
0001

$S$ はサンプル1と同じであるため、$1$ 回目の $M$ シャッフルにおける $\alpha$ と $\sqrt{D}$ はそれぞれ $\frac{1 + \sqrt{2}}{2} = 1.6 \cdots$ と $\sqrt{5} = 2.2 \cdots$ のままです。

しかし $\frac{\alpha^M}{\sqrt{D}} = \frac{\alpha^2}{\sqrt{D}} = 1.1 \cdots$ となるので、その整数部分の下 $4$ 桁は $0001$ となります。

すなわち $S = 0001$ に $M$ シャッフルを施しても $0001$ のままとなり、$M$ シャッフルを $L = 10$ 回繰り返しても $0001$ から変わりません。

サンプル3
入力
0010
4
2
出力
0040

$S = 0010$ が表す非負整数 $n$ は $10$ となります。$2$ 次方程式

$\displaystyle x^2 - n x - 1 = 0 $

は $2$ 実数解が $5 \pm \sqrt{26}$ でそのうちの大きい方 $\alpha$ は $5 + \sqrt{26} = 10.0 \cdots$ となり、判別式 $D$ が $n^2 + 4 = 104$ なので $\sqrt{D}$ は $\sqrt{104} = 10.1 \cdots$ となります。

$\frac{\alpha^M}{\sqrt{D}} = \frac{\alpha^4}{\sqrt{D}} = 1020.0 \cdots$ であるので、その整数部分の下 $4$ 桁は $1020$ となります。

すなわち $S = 0010$ に $M$ シャッフルを施すと $1020$ となり、今回は $L = 2$ なのでもう一度 $M$ シャッフルを施します。

 

置き換わった文字列 $S = 1020$ が表す非負整数 $n$ は $1020$ となります。$2$ 次方程式

$\displaystyle x^2 - n x - 1 = 0 $

は $2$ 実数解が $510 \pm \sqrt{260101}$ でそのうちの大きい方 $\alpha$ は $510 + \sqrt{260101} = 1020.0 \cdots$ となり、判別式 $D$ が $n^2 + 4 = 1040404$ なので $\sqrt{D}$ は $\sqrt{1040404} = 1020.0 \cdots$ となります。

$\frac{\alpha^M}{\sqrt{D}} = \frac{\alpha^4}{\sqrt{D}} = 1061210040.0 \cdots$ であるので、その整数部分の下 $4$ 桁は $0040$ となります。

すなわち $S = 0010$ に $M$ シャッフルを $L = 2$ 回施すと $0040$ となります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。