Growing Baby
National Olympiad — Regional round
Submission name: growingbaby.cpp
Problem summary
A baby starts at mass M. Feeding adds p; a diaper event subtracts q. The first event must be feeding, and between two feedings there may be zero or one diaper event. Count event sequences that end when the mass first reaches at least N. Sleeping does not create additional choices.
Input
M N p q.
Output
The count modulo 2^30.
Constraints
0 < q < p ≤ 100; 2000 ≤ M ≤ 4500 < N ≤ 10000.
Worked example
An independently prepared example for this explanation.
Input
4500 4503 2 1
Output
2
Solution analysis
- Use a state immediately before a mandatory feeding at mass w. If w+p≥N, there is one completion: feed and stop.
- Otherwise choose whether to omit or perform a diaper event before the next feeding, giving states w+p and w+p−q.
- Both successors exceed w, so fill states in descending mass order.
Why it works
Every valid sequence has exactly one of the two choices between consecutive feedings. Reaching the target terminates immediately, excluding extra actions.
Watch out. The modulus is 2^30, not 230. Do not allow a diaper event before the first feeding.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every valid sequence has exactly one of the two choices between consecutive feedings.
// Reaching the target terminates immediately, excluding extra actions.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int m,n,p,q;
cin>>m>>n>>p>>q;
const long long MOD=1LL<<30;
vector<long long>d(n+p+1);
for(int w=n-1;w>=m;w--){
d[w]=w+p>=n?1:(d[w+p]+d[w+p-q])%MOD;
}
cout<<d[m]<<'\n';
}