Bacteria after an Enormous Number of Days
National Olympiad — Municipal round (2018 season)
Submission name: bact.cpp
Problem summary
Start with A bacteria. Each day every bacterium is replaced by B, C bacteria are removed, and the remainder is capped at D. If too few remain for removal the experiment ends. Find the count after K days.
Input
A B C D K.
Output
The final count, or0 if the experiment has ended.
Constraints
0 ≤ A,B,C,D ≤1000; A≤D;1 ≤ K ≤10^18.
Worked example
Input and output for the worked example discussed below.
Input
1 3 1 5 2
Output
5
Solution analysis
- One day maps x to f(x)=min(D,max(0,Bx−C)). Zero is absorbing, including the case where exactly C bacteria are removed and none remain.
- Although K is huge, f is nondecreasing. If the first step increases x, later steps can never decrease it; if it decreases x, later steps can never increase it. An integer orbit bounded between0 and D therefore changes at most D times before stabilizing.
- Simulate until K days have passed or next equals current. At a fixed point every remaining day leaves the count unchanged. The sample goes1→2→5, so day2 has5 bacteria.
Why it works
Monotonicity of f preserves the initial direction of change by induction. A bounded monotone integer sequence must reach a fixed point after at most D changes. Direct simulation is exact before that point, and returning the fixed value is exact for all remaining days.
Watch out. Do not loop up to10^18 or forget the daily cap. Use a64-bit day limit and stop only at a genuine fixed point.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
int count;
int multiplier;
int removed;
int capacity;
long long days;
cin>>count>>multiplier>>removed>>capacity>>days;
for(long long day=0;day<days;day++){
int next=min(capacity,max(0,count*multiplier-removed));
// A fixed point persists for every remaining day.
if(next==count){
break;
}
count=next;
}
cout<<count<<'\n';
}