Official

A - 急増する細菌 / Rapidly Multiplying Bacteria Editorial by admin Editorial for printing

swe-2-high

Explanation

Restating the problem

On day 1 there are \(A\) bacteria, and the count exactly doubles every day. Thus the number of bacteria on day \(i\) is

\[A \cdot 2^{i-1}.\]

We simply need to output this value for \(i = 1, 2, \ldots, N\) in order.

Algorithm

Initialize a variable \(x\) to \(A\) and repeat \(N\) times: print \(x\), then update \(x \leftarrow 2x\).

  • Invariant: just before the \(i\)-th iteration, \(x = A \cdot 2^{i-1}\).
  • Each iteration prints \(x\) before doubling it, so the printed value is exactly \(A \cdot 2^{i-1}\).

Overflow considerations

The largest value occurs at \(i = N\): \(A \cdot 2^{N-1}\). From the constraints \(A \le 10^9\) and \(N \le 30\),

\[A \cdot 2^{N-1} \le 10^9 \cdot 2^{29} = 536{,}870{,}912{,}000{,}000{,}000 \approx 5.4 \times 10^{17},\]

which fits comfortably in a 64-bit signed integer (e.g., C++ long long, up to about \(9.2 \times 10^{18}\)). In Python, integers are arbitrary precision, so no care is needed.

Proof of correctness

Claim: The value printed on the \(i\)-th iteration (1-indexed) is \(A \cdot 2^{i-1}\).

Proof (by induction):

  • Base case: For \(i = 1\), \(x = A = A \cdot 2^0\) before the loop, and it is printed unchanged. Correct.
  • Inductive step: Assume the \(i\)-th printed value is \(A \cdot 2^{i-1}\). After printing, \(x\) is doubled, so at the start of iteration \(i+1\) we have \(x = A \cdot 2^{i-1} \cdot 2 = A \cdot 2^i\), which is printed. Thus iteration \(i+1\) is also correct.

Hence all values for \(i = 1, \ldots, N\) are printed in the correct order. The loop runs exactly \(N\) times producing exactly \(N\) lines, so the output format is satisfied.

Complexity

  • Time: \(O(N)\)
  • Space: \(O(1)\) auxiliary (only two input integers and the current value are stored; the C++ version prints each line immediately. The Python version buffers the output in a list, which is technically \(O(N)\))

posted:
last update: