101161: [AtCoder]ABC116 B - Collatz Problem

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $200$ points

Problem Statement

A sequence $a=\{a_1,a_2,a_3,......\}$ is determined as follows:

  • The first term $s$ is given as input.

  • Let $f(n)$ be the following function: $f(n) = n/2$ if $n$ is even, and $f(n) = 3n+1$ if $n$ is odd.

  • $a_i = s$ when $i = 1$, and $a_i = f(a_{i-1})$ when $i > 1$.

Find the minimum integer $m$ that satisfies the following condition:

  • There exists an integer $n$ such that $a_m = a_n (m > n)$.

Constraints

  • $1 \leq s \leq 100$
  • All values in input are integers.
  • It is guaranteed that all elements in $a$ and the minimum $m$ that satisfies the condition are at most $1000000$.

Input

Input is given from Standard Input in the following format:

$s$

Output

Print the minimum integer $m$ that satisfies the condition.

Sample Input 1

8

Sample Output 1

5

$a=\{8,4,2,1,4,2,1,4,2,1,......\}$. As $a_5=a_2$, the answer is $5$.

Sample Input 2

7

Sample Output 2

18

$a=\{7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,......\}$.

Sample Input 3

54

Sample Output 3

114

Input

题意翻译

定义 $s$ 为如下数列： $\begin{cases}a_{i+1}=\dfrac{a_i}{2}(a_i\equiv0\mod2)\\a_{i+1}=a_i\times3+1(a_i\equiv1\mod2)\end{cases}$ 特殊地，$a_1$ 由输入给出，且满足 $1\leq a_1\leq100$ 。 **注意：不保证运算过程中不会超过 $a_1$ 范围。** 定义正整数 $m$ 存在，当且仅当存在正整数 $n$ 使得 $\begin{cases}a_m=a_n\\m>n\end{cases}$ 成立。 请找出最小的 $m$ 。可以证明，在数据范围内， $m$ 始终存在。

Source/Category

加入题单

算法标签：