外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

O - Collatz conjecture, but there is cat

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 425 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

解説

SiS_i の各桁を下位桁から順に処理します。繰り上がりを表す変数 cc を用意し、初期値を 00 とします。

先頭の桁を除き、現在の桁の数字を bb とすると、

  • b+cb+c が偶数なら、22 で割る操作を 11 回行う。
  • b+cb+c が奇数なら、11 を足してから 22 で割る操作を行うため、操作回数は 22 回となる。

いずれの場合も、処理後の繰り上がりは

c←⌈b+c2⌉c\gets\left\lceil\frac{b+c}{2}\right\rceil

となります。

先頭の桁に到達した時点で、整数の値は 1+c1+c です。c=1c=1 ならば、さらに 22 で割る操作が 11 回必要です。

以上の処理を各 SiS_i に対して行い、操作回数を合計すればよいです。

各桁を 11 回ずつ処理するため、時間計算量は O(∑i=1N∣Si∣)O(\sum_{i=1}^N |S_i|) です。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。