A - 急増する細菌 / Rapidly Multiplying Bacteria Editorial by admin Editorial for printing
gpt-6-astra-mediumOverview
Starting with \(A\) bacteria and doubling the count every day, output the population from day \(1\) to day \(N\) in order.
Analysis
If we know the number of bacteria on a given day, we can find the number on the next day simply by multiplying it by \(2\). Therefore, it suffices to maintain the current bacteria count in a variable x and update it day by day.
For example, when \(N=4,\ A=3\), the number of bacteria will be as follows:
| Day | Number of bacteria |
|---|---|
| Day \(1\) | \(3\) |
| Day \(2\) | \(6\) |
| Day \(3\) | \(12\) |
| Day \(4\) | \(24\) |
In this problem, simply simulating the process for \(N\) days is fast enough. There is no need to track each bacterium individually; it is essential to track only the total population as an integer.
Also, since the count on day \(1\) is \(A\), we should record the current day’s count before doubling it. If we double it first, we would output \(2A\) initially, leading to an incorrect answer.
Algorithm
- Read \(N\) and \(A\).
- Initialize
x, representing the current number of bacteria, to \(A\), and prepare a listoutfor the output. - Repeat the following operation \(N\) times:
- Convert
xto a string and append it toout. - Multiply
xby \(2\) to update it to the count for the next day.
- Convert
- Join the elements of
outwith newlines and print them.
At the beginning of the \(i\)-th iteration, x is \(A \times 2^{i-1}\). Since this is the number of bacteria on day \(i\), this procedure outputs the population for each day in the correct order.
Complexity
- Time Complexity: \(O(N)\)
- Space Complexity: \(O(N)\)
Integer operations and string conversions within the constraints are treated as taking constant time. Since the results for \(N\) days are stored in the output list, the space complexity is \(O(N)\).
Key Implementation Points
By using
range(N), we record the results for exactly \(N\) days.It is crucial to execute
out.append(str(x))beforex *= 2.The number of bacteria on day \(N\) is \(A \times 2^{N-1}\), which may exceed the range of a 32-bit integer. Since Python’s
intsupports arbitrarily large integers, we can compute it directly."\n".join(out)separates the results for each day with newlines and prints them with a trailing newline.Source Code
def main():
import sys
N, A = map(int, sys.stdin.readline().split())
x = A
out = []
for _ in range(N):
out.append(str(x))
x *= 2
sys.stdout.write("\n".join(out) + "\n")
main()
This editorial was generated by gpt-6-astra-medium.
posted:
last update: