問題一覧 > 教育的問題

No.2534 コラッツ数列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 109
作問者 : 👑 p-adicp-adic / テスター : srjywrdnprktsrjywrdnprkt hiro1729hiro1729
0 ProblemId : 9095 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-21 23:47:30

問題文

入力に整数 $N$ が与えられます。

 

整数 $n$ に対する以下の一連の操作を $P(n)$ と呼ぶことにします:

  1. 整数変数 $n'$ の値を $n$ と定める。次の手順に進む。
  2. $n'$ の値が $1$ ならば手順4に進み、そうでないならば次の手順に進む。
  3. $n'$ の値が $2$ で割り切れるならば $n'$ の値を $2^{-1} n'$ の値に置き換え、そうでないならば $n'$ の値を $3n' + 1$ の値に置き換える。手順2に戻る。
  4. 操作を終了する。

定義から $P(n)$ において手順4が実行される回数は高々 $1$ 回です。$P(n)$ において手順4が実行されることを、$P(n)$ が停止すると言います。

$P(n)$ が停止する場合、それまでに手順1,2,3を実行した回数の合計を $P(n)$ の停止ステップ数と呼びます。

$P(n)$ が $50$ ステップ以内に停止するとは、$P(n)$ が停止しかつ $P(n)$ の停止ステップ数が $50$ 以下であるということです。

 

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

入力

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

制約

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

  • $N$ は $-1000 \leq N \leq 1000$ を満たす整数

出力

$P(N)$ が $50$ ステップ以内に停止する場合は、$1$ 行目にYesと出力し、$2$ 行目にその停止ステップ数を出力してください。

$P(N)$ が停止しない場合は、Noと出力してください。

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

サンプル

サンプル1
入力
0
出力
No

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

手順1: $n' = 0$
手順2: $n' = 0$
手順3: $n' = 0$
手順2: $n' = 0$
手順3: $n' = 0$
手順2: $n' = 0$
手順3: $n' = 0$
手順2: $n' = 0$
手順3: $n' = 0$
手順2: $n' = 0$
手順3: $n' = 0$
$\vdots$

となり、$P(0)$ は停止しません。特に $P(0)$ は $50$ ステップ以内には停止しません。

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

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

手順1: $n' = 1$
手順2: $n' = 1$
手順4: $n' = 1$

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

サンプル3
入力
2
出力
Yes
4

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

手順1: $n' = 2$
手順2: $n' = 2$
手順3: $n' = 1$
手順2: $n' = 1$
手順4: $n' = 1$

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

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