概要

増殖を \(K\) 回行ったときに、培養液中に現れる「コロニーサイズの異なる値」が何種類あるかを求めます。

考察

増殖のルールは「今ある各コロニーから、サイズが \(2\) 倍の新しいコロニーが1つ生まれ、元のコロニーも残る」です。

ここで重要なのは、サイズの変化が常に「2倍」しか起こらないことです。初期状態はサイズ \(1\) のみなので、そこから作られるサイズは

• 1回増殖後：\(1\) から \(2\) が生まれる → サイズは \(\{1, 2\}\)
• 2回増殖後：\(1\) から \(2\)、\(2\) から \(4\) が生まれる → サイズは \(\{1, 2, 4\}\)
• 3回増殖後：\(\{1, 2, 4, 8\}\)

というように、常に \(1, 2, 4, 8, \dots\) と \(2\) のべき乗だけが登場します。

より一般に、\(i\) 回増殖が終わった時点で存在しうるサイズは $\( \{2^0, 2^1, 2^2, \dots, 2^i\} \)$ となります（帰納法で示せます）：

• \(i=0\)（開始時）：\(\{2^0\}=\{1\}\) で成立
• \(i\) 回後に \(\{2^0,\dots,2^i\}\) があるとすると、次の増殖で各サイズ \(2^j\) から \(2^{j+1}\) が生まれる
  つまり新たに追加される可能性があるのは最大で \(2^{i+1}\) で、集合は \(\{2^0,\dots,2^{i+1}\}\) になる

したがって、\(K\) 回後の種類数（異なるサイズの個数）は $\( K+1 \)$ です。

なお、素朴に「コロニーを全部生成して管理する」と、コロニー数は毎回倍増して \(2^K\) 個になり、\(K \le 10^{18}\) では到底扱えません（TLE/メモリ不足）。しかし本問は「種類数」だけなので、上の規則性により即座に答えが出ます。

アルゴリズム

1. 入力で \(K\) を受け取る
2. \(K+1\) を出力する

計算量

• 時間計算量: \(O(1)\)
• 空間計算量: \(O(1)\)

実装のポイント

• \(K\) は最大 \(10^{18}\) なので、シミュレーションは不要かつ不可能です。答えは必ず \(K+1\) になります。

• Python の int は大きな整数を扱えるため、そのまま K + 1 を出力すれば十分です。

  ソースコード

import sys

K = int(sys.stdin.readline().strip())
print(K + 1)

この解説は gpt-5.2-high によって生成されました。