Official

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

swe-2-high

\(i\) 日目の細菌の数は \(A \times 2^{i-1}\) 匹です。プログラムは現在の数を変数に持ち、出力するたびに2倍して次の日の数を作る、という処理を \(N\) 回繰り返します。1日前の数に2を掛けるだけで翌日の数が正しく得られるので、これは定義をそのままシミュレーションしたものです。最大でも \(A \times 2^{29}\) で約 \(5 \times 10^{17}\) となり、64ビット整数(long long)に収まります。ループは \(N\) 回なので時間計算量は \(O(N)\)、記憶するのは現在の数だけで空間計算量は \(O(1)\) です。

posted:
last update: