公式

A - 急増する細菌 / Rapidly Multiplying Bacteria 解説 by admin 印刷ページ

gpt-6-astra-medium

Overview

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

  1. Read \(N\) and \(A\).
  2. Initialize x, representing the current number of bacteria, to \(A\), and prepare a list out for the output.
  3. Repeat the following operation \(N\) times:
    • Convert x to a string and append it to out.
    • Multiply x by \(2\) to update it to the count for the next day.
  4. Join the elements of out with 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)) before x *= 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 int supports 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.

投稿日時:
最終更新: