No.2122 黄金比で擬似乱数生成
タグ : / 解いたユーザー数 23
作問者 : 👑
p-adic
/ テスター :
googol_S0
shino16
問題文
入力に文字 $0$ ～ $9$ のみからなる長さ $4$ の文字列 $S$ と非負整数 $M,L$ が与えられます。
非負整数 $m$ に対し、文字 $0$ ～ $9$ のみからなる長さ $4$ の文字列 $s$ に対する以下の一連の操作をここでは $m$ シャッフルと呼ぶことにします：
- $s$ が表す非負整数を $n$ と置く。
- $2$ 次方程式 $x^2 - nx - 1 = 0$ の $2$ 実数解のうち大きい方を $\alpha$ と置き、判別式を $D$ と置く。
- $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もしくは右上の雲マークをクリックしてアカウントを作成してください。