CF 198A - About Bacteria
The problem involves modeling bacterial growth in a test tube according to a discrete-time recurrence. Each bacterium splits into k bacteria every second, and an additional b bacteria are added due to abnormal effects.
Rating: 1700
Tags: implementation, math
Solve time: 35s
Verified: no
Solution
Problem Understanding
The problem involves modeling bacterial growth in a test tube according to a discrete-time recurrence. Each bacterium splits into k bacteria every second, and an additional b bacteria are added due to abnormal effects. After n seconds starting from one bacterium, the first experiment reaches exactly z bacteria. The second experiment starts with t bacteria, and we want to determine the minimum number of seconds required for the same growth process to reach at least z bacteria.
The inputs k, b, n, and t are all integers between 1 and 10^6. This implies that any iterative computation over time should avoid linear scans of z or large loops up to z, because the number of bacteria can grow extremely fast - exponentially in n for the multiplicative factor k. Overflow is not an issue in Python, but in other languages, care would be needed. The output is a single integer, representing the number of seconds.
Edge cases arise when the starting number of bacteria t is already equal to or greater than the target z. For example, if t = z, the answer sh