Next Simultaneous Biorhythm Peak
National Olympiad — Regional round (2017 season)
Submission name: bio.cpp
Problem summary
Cycles have periods23,28,33 days. Given a peak date for each and a reference date, find the strictly later next simultaneous peak.
Input
Four day/month dates in2017: physical,emotional,intellectual peak and reference.
Output
The positive delay in days.
Constraints
Dates are valid in non-leap2017; the reference need not be latest.
Worked example
Input and output for the worked example discussed below.
Input
1/1 1/1 1/1 1/1
Output
21252
Solution analysis
- Convert each date into its ordinal day by summing lengths of preceding months. Differences between these ordinals correctly count elapsed days.
- Test delays1…21252. A candidate day t is a peak for period P exactly when t−knownPeak is divisible by P. Return the first day satisfying all three congruences.
- The periods are pairwise coprime with product21252, so a unique common residue occurs in this interval. If all dates are1/1, the current peak is excluded and the answer is the full21252-day period.
Why it works
The divisibility tests express exactly the periodic peak sets. Pairwise coprime periods guarantee a common residue modulo their product. Increasing positive delay therefore finds the earliest permitted common peak within the bound.
Watch out. February2017 has28 days. Begin at delay1. A negative date difference is still valid if divisible by its period.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int readDay(){
string date;
cin>>date;
size_t slash=date.find('/');
int day=stoi(date.substr(0,slash));
int month=stoi(date.substr(slash+1));
const int lengths[12]={31,28,31,30,31,30,31,31,30,31,30,31};
for(int i=0;i<month-1;i++){
day+=lengths[i];
}
return day;
}
int main(){
int physical=readDay();
int emotional=readDay();
int intellectual=readDay();
int reference=readDay();
// Exclude a triple peak on the reference day itself.
for(int delay=1;delay<=21252;delay++){
int day=reference+delay;
if((day-physical)%23==0&&(day-emotional)%28==0&&(day-intellectual)%33==0){
cout<<delay<<'\n';
break;
}
}
}