No.2787 Goodstein Sequence?
タグ : / 解いたユーザー数 7
作問者 : 👑
testestest
googol_S0
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)$:
- Set the values of the integer variables $n'$ and $b'$ to $n$ and $b$, respectively. Proceed to the next step.
- If the value of $n'$ is positive, proceed to the next step; otherwise, proceed to step 4.
- 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.
- 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
Yeson line $1$. - If $P(N,B)$ halts within $C$ steps, print
Yeson line $2$, and print its halting step count on line $3$. - If $P(N,B)$ does not halt within $C$ steps, print
Noon line $2$. - If $P(N,B)$ does not halt, print
Noon 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もしくは右上の雲マークをクリックしてアカウントを作成してください。