問題一覧 > 教育的問題

No.2787 Goodstein Sequence?

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 7
作問者 : 👑 p-adic / テスター : testestest googol_S0
お気に入りにしたユーザー ProblemId : 8731 / 自分の提出
問題文最終更新日: 2024-06-23 12:39:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 433 (順位表) の他の問題:

Problem Statement

First, we introduce some notation and terminology. For a non-negative integer $n$ and an integer $b$ greater than or equal to $2$, define the non-negative integer $G_b(n)$ by the following recurrence:

$\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. $

Here, $n \bmod b$ denotes the remainder when $n$ is divided by $b$.

For a non-negative integer $n$ and an integer $b$ greater than or equal to $2$, we call the following series of operations $P(n,b)$:

  1. Set the values of the integer variables $n'$ and $b'$ to $n$ and $b$, respectively. Proceed to the next step.
  2. If the value of $n'$ is positive, proceed to the next step; otherwise, proceed to step 4.
  3. Replace the value of $n'$ with the value of $G_{b'}(n') - 1$. Replace the value of $b'$ with $b' + 1$. Return to step 2.
  4. End the operations.

By definition, step 4 is executed at most $1$ time in $P(n,b)$. We say that $P(n,b)$ halts if step 4 is executed in $P(n,b)$. If $P(n,b)$ halts, the total number of times steps 1,2,3 have been executed up to that point is called the halting step count of $P(n,b)$.

For a non-negative integer $c$, we say that $P(n,b)$ halts within $c$ steps if $P(n,b)$ halts and the halting step count of $P(n,b)$ is at most $c$.

 

You are given as input a non-negative integer $N$, an integer $B$ greater than or equal to $2$, and a non-negative integer $C$.

Determine whether $P(N,B)$ halts. If it halts, determine whether it halts within $C$ steps. If it halts within $C$ steps, find its halting step count.

Background

Let $n$ be a non-negative integer and $b$ be an integer greater than or equal to $2$. If $n$ is less than $b^b$, the transition of $n'$ in $P(n,b)$ is nothing other than the sequence obtained by using $b$ instead of $2$ as the initial base in the definition of the Goodstein sequence with first term $n$.

Input

The input is given from standard input in the following format:

$N$ $B$ $C$

$N, B, C$ are given on $1$ line, separated by single spaces.

Constraints

The input satisfies the following constraints:

  • $N$ is a non-negative integer at most $10^{18}$
  • $B$ is an integer between $2$ and $10^{18}$, inclusive
  • $C$ is a non-negative integer at most $10^{18}$

Output

Output in the following format:

  • If $P(N,B)$ halts, print Yes on line $1$.
    • If $P(N,B)$ halts within $C$ steps, print Yes on line $2$, and print its halting step count on line $3$.
    • If $P(N,B)$ does not halt within $C$ steps, print No on line $2$.
  • If $P(N,B)$ does not halt, print No on line $1$.

Print a newline at the end.

Sample

Sample 1
Input
1 2 10
Output
Yes
Yes
4

The step numbers in the operations $P(1,2)$ and the values of the integer variables $n', b'$ after each step change as follows:

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

Thus, $P(1,2)$ halts and its halting step count is $4$. In particular, it halts within $10$ steps.

Sample 2
Input
4 2 10
Output
Yes
No

The step numbers in the operations $P(4,2)$ and the values of the integer variables $n', b'$ after each step change as follows:

手順1: $(n',b') = (4,2)$
手順2: $(n',b') = (4,2)$
手順3: $(n',b') = (G_2(4)-1,3) = (8,3)$
手順2: $(n',b') = (8,3)$
手順3: $(n',b') = (G_3(8)-1,4) = (9,4)$
手順2: $(n',b') = (9,4)$
手順3: $(n',b') = (G_4(9)-1,5) = (10,5)$
手順2: $(n',b') = (10,5)$
手順3: $(n',b') = (G_5(10)-1,6) = (11,6)$
手順2: $(n',b') = (11,6)$
手順3: $(n',b') = (G_6(11)-1,7) = (11,7)$
手順2: $(n',b') = (11,7)$
手順3: $(n',b') = (G_7(11)-1,8) = (11,8)$
手順2: $(n',b') = (11,8)$
手順3: $(n',b') = (G_8(11)-1,9) = (11,9)$
手順2: $(n',b') = (11,9)$
手順3: $(n',b') = (G_9(11)-1,10) = (11,10)$
手順2: $(n',b') = (11,10)$
手順3: $(n',b') = (G_{10}(11)-1,11) = (11,11)$
手順2: $(n',b') = (11,11)$
手順3: $(n',b') = (G_{11}(11)-1,12) = (11,12)$
手順2: $(n',b') = (11,12)$
手順3: $(n',b') = (G_{12}(11)-1,13) = (10,13)$
手順2: $(n',b') = (10,13)$
手順3: $(n',b') = (G_{13}(10)-1,14) = (9,14)$
手順2: $(n',b') = (9,14)$
手順3: $(n',b') = (G_{14}(9)-1,15) = (8,15)$
手順2: $(n',b') = (8,15)$
手順3: $(n',b') = (G_{15}(8)-1,16) = (7,16)$
手順2: $(n',b') = (7,16)$
手順3: $(n',b') = (G_{16}(7)-1,17) = (6,17)$
手順2: $(n',b') = (6,17)$
手順3: $(n',b') = (G_{17}(6)-1,18) = (5,18)$
手順2: $(n',b') = (5,18)$
手順3: $(n',b') = (G_{18}(5)-1,19) = (4,19)$
手順2: $(n',b') = (4,19)$
手順3: $(n',b') = (G_{19}(4)-1,20) = (3,20)$
手順2: $(n',b') = (3,20)$
手順3: $(n',b') = (G_{20}(3)-1,21) = (2,21)$
手順2: $(n',b') = (2,21)$
手順3: $(n',b') = (G_{21}(2)-1,22) = (1,22)$
手順2: $(n',b') = (1,22)$
手順3: $(n',b') = (G_{22}(1)-1,23) = (0,23)$
手順2: $(n',b') = (0,23)$
手順4: $(n',b') = (0,23)$

Thus, $P(4,2)$ halts and its halting step count is $44$. In particular, it does not halt within $10$ steps.

Sample 3
Input
3 3 10
Output
Yes
Yes
10

The step numbers in the operations $P(3,3)$ and the values of the integer variables $n', b'$ after each step change as follows:

手順1: $(n',b') = (3,3)$
手順2: $(n',b') = (3,3)$
手順3: $(n',b') = (G_3(3)-1,4) = (3,4)$
手順2: $(n',b') = (3,4)$
手順3: $(n',b') = (G_4(3)-1,5) = (2,5)$
手順2: $(n',b') = (2,5)$
手順3: $(n',b') = (G_5(2)-1,6) = (1,6)$
手順2: $(n',b') = (1,6)$
手順3: $(n',b') = (G_6(1)-1,7) = (0,7)$
手順2: $(n',b') = (0,7)$
手順4: $(n',b') = (0,7)$

Thus, $P(3,3)$ halts and its halting step count is $10$. In particular, it halts within $10$ steps.

Sample 4
Input
8 2 1000000000000000000
Output
Yes
No

The operations $P(8,2)$ halt, but the halting step count exceeds at least $10^{10^8}$. In particular, it does not halt within $10^{18}$ steps.

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