A - 急増する細菌 / Rapidly Multiplying Bacteria Editorial by admin Editorial for printing
gpt-6-astra-mediumOverview
Print the number of bacteria for the current day and double it for the next day, repeating this operation \(N\) times.
Analysis
Since the number of bacteria doubles exactly every day, we can determine the count for any day as long as we know the previous day’s count. The number of bacteria on the \(i\)-th day is \(A \times 2^{i-1}\), but there is no need to compute the power from scratch each time.
For example, when \(N=4,\ A=3\), the number of bacteria changes as follows:
- Day \(1\): \(3\) bacteria
- Day \(2\): \(6\) bacteria
- Day \(3\): \(12\) bacteria
- Day \(4\): \(24\) bacteria
Therefore, it is sufficient to store only the current count in a variable and print it sequentially. This naive simulation easily runs within the time limit.
However, care must be taken regarding the size of the integer type. The maximum value to be printed is \(10^9 \times 2^{29}\), which does not fit in the standard \(32\)-bit signed integer type int in C++. To prevent wrong answers due to integer overflow, use long long for the number of bacteria.
Algorithm
- Read the number of days \(N\) and the initial number of bacteria \(A\).
- Initialize a variable
cur, representing the current number of bacteria, to \(A\). - Repeat the following operation \(N\) times:
- Print
cur. - Update it to the next day’s count by setting
cur = cur + cur.
- Print
At the first output, cur is \(A\). Since it is doubled after each output, the number of bacteria for each day will be printed in order.
Complexity
- Time complexity: \(O(N)\)
- Space complexity: \(O(1)\)
For each day, we perform one output and one update. Furthermore, there is no need to store the values for all days in an array.
Implementation Details
Print before doubling. If you double it first, the output for the first day would incorrectly be \(2A\).
Run the loop exactly \(N\) times, printing a newline after each value.
Use
long longforato store the input value and forcurto store the current count.In the reference code, an update is performed even after printing on the final day. That value can reach up to \(10^9 \times 2^{30}\), but this also safely fits within the range of
long long.Source Code
// 問題文から独立に実装: 前日の値を足して 2 倍にする
#include <iostream>
int main() {
int n; long long a; std::cin >> n >> a;
long long cur = a;
for (int i = 0; i < n; ++i) { std::cout << cur << "\n"; cur = cur + cur; }
}
This editorial was generated by gpt-6-astra-medium.
posted:
last update: