問題一覧 > 教育的問題

No.2787 グッドスタイン数列？

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 7
作問者 : 👑 p-adic / テスター : 👑 testestest googol_S0
1 ProblemId : 8731 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-06-23 12:39:28

問題文

まず記法と用語を導入します。非負整数 nn と 22 以上の整数 bb に対し、非負整数 Gb(n)G_b(n) を次の再帰式で定めます：

Gb(n)={n(n<b)Gb(n−(n mod b)b)×(b+1)+(n mod b)(n≥b)\displaystyle G_b(n) = \left\{ \begin{array}{ll} \displaystyle n &\displaystyle (n < b) \\ \displaystyle G_b \left(\frac{n - (n \bmod b)}{b} \right) \times (b + 1) + (n \bmod b) &\displaystyle (n \geq b) \end{array} \right.

ただし n mod bn \bmod b で nn を bb で割った余りを表します。

非負整数 nn と 22 以上の整数 bb に対する以下の一連の操作を P(n,b)P(n,b) と呼ぶことにします：

  1. 整数変数 n′n' と b′b' の値を nn と bb と定める。次の手順に進む。
  2. n′n' の値が正であるならば次の手順に進み、そうでないならば手順4に進む。
  3. n′n' の値を Gb′(n′)−1G_{b'}(n') - 1 の値に置き換える。b′b' の値を b′+1b' + 1 に置き換える。手順2に戻る。
  4. 操作を終了する。

定義から P(n,b)P(n,b) において手順4が実行される回数は高々 11 回です。P(n,b)P(n,b) において手順4が実行されることを、P(n,b)P(n,b) が停止すると言います。P(n,b)P(n,b) が停止する場合、それまでに手順1,2,3を実行した回数の合計を P(n,b)P(n,b) の停止ステップ数と呼びます。

非負整数 cc に対し、P(n,b)P(n,b) が cc ステップ以内に停止するとは、P(n,b)P(n,b) が停止しかつ P(n,b)P(n,b) の停止ステップ数が cc 以下であるということです。

　

入力に非負整数 NN と 22 以上の整数 BB と非負整数 CC が与えられます。

P(N,B)P(N,B) が停止するか否かを判定し、停止する場合は CC ステップ以内に停止するか否かを判定し、CC ステップ以内に停止する場合はその停止ステップ数を求めてください。

背景

nn を非負整数とし、bb を 22 以上の整数とします。もし nn が bbb^b 未満であるならば、P(n,b)P(n,b) における n′n' の遷移は初項 nn のグッドスタイン数列の定義で 22 の代わりに bb を最初の基数として用いて得られる数列に他なりません。

入力

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

NN BB CC

11 行に N,B,CN, B, C が半角空白区切りで与えられます。

制約

入力は以下の制約を満たします：

  • NN は 101810^{18} 以下の非負整数
  • BB は 22 以上 101810^{18} 以下の整数
  • CC は 101810^{18} 以下の非負整数

出力

以下の形式で出力してください：

  • P(N,B)P(N,B) が停止するならば、11 行目にYesと出力してください。
    • P(N,B)P(N,B) が CC ステップ以内に停止するならば、22 行目にYesと出力し、33 行目にその停止ステップ数を出力してください。
    • P(N,B)P(N,B) が CC ステップ以内に停止しないならば、22 行目にNoと出力してください。
  • P(N,B)P(N,B) が停止しないならば、11 行目にNoと出力してください。

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

サンプル

サンプル1
入力
1 2 10
出力
Yes
Yes
4

操作 P(1,2)P(1,2) における手順番号と手順実行後の整数変数 n′,b′n', b' の値の変遷を書くと 

手順1: (n′,b′)=(1,2)(n',b') = (1,2)
手順2: (n′,b′)=(1,2)(n',b') = (1,2)
手順3: (n′,b′)=(G2(1)−1,3)=(0,3)(n',b') = (G_2(1)-1,3) = (0,3)
手順2: (n′,b′)=(0,3)(n',b') = (0,3)
手順4: (n′,b′)=(0,3)(n',b') = (0,3)

となり、P(1,2)P(1,2) は停止してその停止ステップ数は 44 です。特に 1010 ステップ以内に停止します。

サンプル2
入力
4 2 10
出力
Yes
No

操作 P(4,2)P(4,2) における手順番号と手順実行後の整数変数 n′,b′n', b' の値の変遷を書くと 

手順1: (n′,b′)=(4,2)(n',b') = (4,2)
手順2: (n′,b′)=(4,2)(n',b') = (4,2)
手順3: (n′,b′)=(G2(4)−1,3)=(8,3)(n',b') = (G_2(4)-1,3) = (8,3)
手順2: (n′,b′)=(8,3)(n',b') = (8,3)
手順3: (n′,b′)=(G3(8)−1,4)=(9,4)(n',b') = (G_3(8)-1,4) = (9,4)
手順2: (n′,b′)=(9,4)(n',b') = (9,4)
手順3: (n′,b′)=(G4(9)−1,5)=(10,5)(n',b') = (G_4(9)-1,5) = (10,5)
手順2: (n′,b′)=(10,5)(n',b') = (10,5)
手順3: (n′,b′)=(G5(10)−1,6)=(11,6)(n',b') = (G_5(10)-1,6) = (11,6)
手順2: (n′,b′)=(11,6)(n',b') = (11,6)
手順3: (n′,b′)=(G6(11)−1,7)=(11,7)(n',b') = (G_6(11)-1,7) = (11,7)
手順2: (n′,b′)=(11,7)(n',b') = (11,7)
手順3: (n′,b′)=(G7(11)−1,8)=(11,8)(n',b') = (G_7(11)-1,8) = (11,8)
手順2: (n′,b′)=(11,8)(n',b') = (11,8)
手順3: (n′,b′)=(G8(11)−1,9)=(11,9)(n',b') = (G_8(11)-1,9) = (11,9)
手順2: (n′,b′)=(11,9)(n',b') = (11,9)
手順3: (n′,b′)=(G9(11)−1,10)=(11,10)(n',b') = (G_9(11)-1,10) = (11,10)
手順2: (n′,b′)=(11,10)(n',b') = (11,10)
手順3: (n′,b′)=(G10(11)−1,11)=(11,11)(n',b') = (G_{10}(11)-1,11) = (11,11)
手順2: (n′,b′)=(11,11)(n',b') = (11,11)
手順3: (n′,b′)=(G11(11)−1,12)=(11,12)(n',b') = (G_{11}(11)-1,12) = (11,12)
手順2: (n′,b′)=(11,12)(n',b') = (11,12)
手順3: (n′,b′)=(G12(11)−1,13)=(10,13)(n',b') = (G_{12}(11)-1,13) = (10,13)
手順2: (n′,b′)=(10,13)(n',b') = (10,13)
手順3: (n′,b′)=(G13(10)−1,14)=(9,14)(n',b') = (G_{13}(10)-1,14) = (9,14)
手順2: (n′,b′)=(9,14)(n',b') = (9,14)
手順3: (n′,b′)=(G14(9)−1,15)=(8,15)(n',b') = (G_{14}(9)-1,15) = (8,15)
手順2: (n′,b′)=(8,15)(n',b') = (8,15)
手順3: (n′,b′)=(G15(8)−1,16)=(7,16)(n',b') = (G_{15}(8)-1,16) = (7,16)
手順2: (n′,b′)=(7,16)(n',b') = (7,16)
手順3: (n′,b′)=(G16(7)−1,17)=(6,17)(n',b') = (G_{16}(7)-1,17) = (6,17)
手順2: (n′,b′)=(6,17)(n',b') = (6,17)
手順3: (n′,b′)=(G17(6)−1,18)=(5,18)(n',b') = (G_{17}(6)-1,18) = (5,18)
手順2: (n′,b′)=(5,18)(n',b') = (5,18)
手順3: (n′,b′)=(G18(5)−1,19)=(4,19)(n',b') = (G_{18}(5)-1,19) = (4,19)
手順2: (n′,b′)=(4,19)(n',b') = (4,19)
手順3: (n′,b′)=(G19(4)−1,20)=(3,20)(n',b') = (G_{19}(4)-1,20) = (3,20)
手順2: (n′,b′)=(3,20)(n',b') = (3,20)
手順3: (n′,b′)=(G20(3)−1,21)=(2,21)(n',b') = (G_{20}(3)-1,21) = (2,21)
手順2: (n′,b′)=(2,21)(n',b') = (2,21)
手順3: (n′,b′)=(G21(2)−1,22)=(1,22)(n',b') = (G_{21}(2)-1,22) = (1,22)
手順2: (n′,b′)=(1,22)(n',b') = (1,22)
手順3: (n′,b′)=(G22(1)−1,23)=(0,23)(n',b') = (G_{22}(1)-1,23) = (0,23)
手順2: (n′,b′)=(0,23)(n',b') = (0,23)
手順4: (n′,b′)=(0,23)(n',b') = (0,23)

となり、P(4,2)P(4,2) は停止してその停止ステップ数は 4444 です。特に 1010 ステップ以内には停止しません。

サンプル3
入力
3 3 10
出力
Yes
Yes
10

操作 P(3,3)P(3,3) における手順番号と手順実行後の整数変数 n′,b′n', b' の値の変遷を書くと 

手順1: (n′,b′)=(3,3)(n',b') = (3,3)
手順2: (n′,b′)=(3,3)(n',b') = (3,3)
手順3: (n′,b′)=(G3(3)−1,4)=(3,4)(n',b') = (G_3(3)-1,4) = (3,4)
手順2: (n′,b′)=(3,4)(n',b') = (3,4)
手順3: (n′,b′)=(G4(3)−1,5)=(2,5)(n',b') = (G_4(3)-1,5) = (2,5)
手順2: (n′,b′)=(2,5)(n',b') = (2,5)
手順3: (n′,b′)=(G5(2)−1,6)=(1,6)(n',b') = (G_5(2)-1,6) = (1,6)
手順2: (n′,b′)=(1,6)(n',b') = (1,6)
手順3: (n′,b′)=(G6(1)−1,7)=(0,7)(n',b') = (G_6(1)-1,7) = (0,7)
手順2: (n′,b′)=(0,7)(n',b') = (0,7)
手順4: (n′,b′)=(0,7)(n',b') = (0,7)

となり、P(3,3)P(3,3) は停止してその停止ステップ数は 1010 です。特に 1010 ステップ以内に停止します。

サンプル4
入力
8 2 1000000000000000000
出力
Yes
No

操作 P(8,2)P(8,2) は停止しますが、その停止ステップ数は少なくとも 1010810^{10^8} を超えます。特に 101810^{18} ステップ以内には停止しません。

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