Alternating Aquarium Growth
National Olympiad — Municipal round (2012 season)
Submission name: fish_globe.cpp
Problem summary
An aquarium begins with K silver fish. Global days alternate: silver fish change colour, then gold fish each produce one silver fish. Find the total after N days of the repeating process.
Input
Initial fish count K and number of days N.
Output
The total fish count after N days.
Constraints
2 ≤ K ≤ 24; 2 ≤ N ≤ 65.
Worked example
Input and output for the worked example discussed below.
Input
5 7
Output
40
Solution analysis
- The described process alternates its two global stages. On a colour-change day the population is unchanged. On a birth day every existing gold fish produces one new fish, doubling the total.
- Every complete pair of days therefore multiplies the population by 2. There are floor(N/2) completed pairs; an additional colour-change day has no effect on the total.
- Starting with 5 fish, totals after days 1…7 are 5,10,10,20,20,40,40. Hence the sample answer is 40. Compute K×2^floor(N/2) with integer multiplication, not a daily Fibonacci model.
Why it works
After each birth stage there are equal numbers of gold parents and silver newborns. The next colour stage turns all remaining silver fish gold, so the next birth stage doubles the entire current population again. Induction over complete two-day cycles gives K×2^floor(N/2).
Watch out. Do not let newborn fish reproduce immediately. The stages are global alternating days, not independent per-fish age counters. An odd final day changes colours only.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
long long fish;
int days;
cin>>fish>>days;
// Only completed two-day cycles contain a birth stage.
for(int cycle=0;cycle<days/2;cycle++){
fish*=2;
}
cout<<fish<<'\n';
}