A - 急増する細菌 / Rapidly Multiplying Bacteria Editorial by admin Editorial for printing
gpt-6-astra-mediumOverview
Starting with \(A\) bacteria on day \(1\), the number of bacteria doubles every day. Following this rule, output the number of bacteria from day \(1\) to day \(N\) in order.
Analysis
Writing out the number of bacteria for each day gives the following:
- Day \(1\): \(A\)
- Day \(2\): \(A \times 2\)
- Day \(3\): \(A \times 2^2\)
By day \(i\), the number of bacteria has doubled \(i-1\) times, so the number of bacteria on day \(i\) can be calculated as:
\(A \times 2^{i-1}\)
For example, when \(N=4,\ A=3\), the numbers to output in order are \(3,\ 6,\ 12,\ 24\).
In this problem, a naive approach that computes the value for each day directly easily runs well within the time limit. No special optimizations are necessary. However, since the bacteria have not yet multiplied on day \(1\), setting the exponent to \(i\) instead would result in an answer twice as large, leading to a wrong answer.
Algorithm
- Read \(N\) and \(A\).
- Iterate the variable
ifrom \(0\) to \(N-1\) in order. - For each
i, compute and output \(A \times 2^i\).
In the code, i represents “how many days have passed since day \(1\)”. Therefore, when i = 0, it outputs the count for day \(1\), and when i = N-1, it outputs the count for day \(N\).
Complexity
- Time complexity: \(O(N)\) (assuming integer arithmetic and exponentiation within the constraints take constant time)
- Space complexity: \(O(1)\) (the output values do not need to be stored in an array or similar container)
Implementation Notes
In Python,
**represents exponentiation. You can compute \(2^i\) using2 ** i. Note that^is the bitwise XOR operator, not exponentiation.range(n)generates values from \(0\) to \(N-1\), allowing you to output exactly \(N\) lines.The number of bacteria can reach up to \(10^9 \times 2^{29}\), which does not fit in a signed \(32\)-bit integer. Since Python can handle arbitrarily large integers automatically, no special measures are required in this code.
Source Code
# 問題文から独立に実装
n, a = map(int, input().split())
for i in range(n):
print(a * 2 ** i)
This editorial was generated by gpt-6-astra-medium.
posted:
last update: