Overview

We want to find how many distinct colony sizes appear in the culture medium after performing proliferation \(K\) times.

Analysis

The rule of proliferation is: “From each existing colony, a new colony with double the size is born, and the original colony also remains.”

The key observation here is that the only size change that ever occurs is “doubling.” Since the initial state consists of only size \(1\), the sizes produced from it are:

• After 1 proliferation: \(2\) is born from \(1\) → sizes are \(\{1, 2\}\)
• After 2 proliferations: \(2\) is born from \(1\), \(4\) is born from \(2\) → sizes are \(\{1, 2, 4\}\)
• After 3 proliferations: \(\{1, 2, 4, 8\}\)

In this way, only powers of \(2\): \(1, 2, 4, 8, \dots\) ever appear.

More generally, the set of possible sizes after \(i\) proliferations is $\( \{2^0, 2^1, 2^2, \dots, 2^i\} \)$ (This can be shown by induction):

• \(i=0\) (initial state): \(\{2^0\}=\{1\}\), which holds.
• If after \(i\) proliferations we have \(\{2^0,\dots,2^i\}\), then in the next proliferation, each size \(2^j\) gives birth to \(2^{j+1}\).
  That is, the largest new size that can be added is at most \(2^{i+1}\), so the set becomes \(\{2^0,\dots,2^{i+1}\}\).

Therefore, the number of distinct sizes after \(K\) proliferations is $\( K+1 \)$

Note that if you naively “generate and manage all colonies,” the number of colonies doubles each time, reaching \(2^K\), which is completely infeasible for \(K \le 10^{18}\) (TLE/out of memory). However, since this problem only asks for the “number of distinct sizes,” the pattern above gives us the answer immediately.

Algorithm

1. Read \(K\) from input.
2. Output \(K+1\).

Complexity

• Time complexity: \(O(1)\)
• Space complexity: \(O(1)\)

Implementation Notes

• Since \(K\) can be up to \(10^{18}\), simulation is both unnecessary and impossible. The answer is always \(K+1\).

• Python’s int can handle arbitrarily large integers, so simply outputting K + 1 is sufficient.

  Source Code

import sys

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

This editorial was generated by gpt-5.2-high.