Rabbit Deliveries
Autumn Tournament (2016)
Submission name: rabbit.cpp
Problem summary
A rabbit starts beside x cabbages and carries them home one at a time. Each one-way journey takes n days; it returns for another cabbage after every delivery except the last. Given the starting date, find the finishing date, counting the starting date as the first travel day, as in the sample.
Source clarification. The prose does not explicitly define inclusive day counting, but the official sample requires it: nine journeys of three days starting June 3 finish June 29, not June 30. The summary and solution explicitly follow this sample convention.
Input
x and n, then day d, month m and year g of the starting date.
Output
Finishing day, month and year separated by spaces.
Constraints
2 ≤ x ≤ 5; 1 ≤ n ≤ 3; 1 ≤ d ≤ 31; 1 ≤ m ≤ 12; 1900 ≤ g ≤ 2100. The input describes a valid calendar date.
Worked example
Original statement sample.
Input
5 3 3 6 2017
Output
29 6 2017
Solution analysis
- There are x outbound trips carrying a cabbage and x−1 return trips. Thus travel occupies (2x−1)n calendar days. Because the starting date is counted as day one, advance the date (2x−1)n−1 times.
- Advance one day at a time. If the day exceeds the current month length, reset it to 1 and advance the month; after December, reset the month to January and increase the year. February has 29 days exactly when the year is divisible by 400 or divisible by 4 but not by 100.
- For x=5 and n=3 there are 27 travel days. June 3 is day one, so 26 day increments lead to June 29, matching the sample.
Why it works
There are exactly x carrying trips and x−1 necessary returns, with no final return. Inclusive counting places the last of their (2x−1)n days that many minus one increments after the first date. Each update replaces a date by its next Gregorian date, so induction over the increments proves the final result.
Watch out. Use the full Gregorian leap-year rule: 1900 and 2100 are not leap years, but 2000 is. Preserve the sample’s inclusive starting-day convention.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: There are exactly x carrying trips and x−1 necessary returns, with no final return.
// Inclusive counting places the last of their (2x−1)n days that many minus one increments after the
// first date.
#include<iostream>
using namespace std;
bool leapYear(int year){
return year%400==0||(year%4==0&&year%100!=0);
}
int main(){
int cabbages,journey,day,month,year;
cin>>cabbages>>journey>>day>>month>>year;
int increments=(2*cabbages-1)*journey-1;
const int length[12]={31,28,31,30,31,30,31,31,30,31,30,31};
for(int step=0;step<increments;++step){
int monthLength=length[month-1];
if(month==2&&leapYear(year)){
++monthLength;
}
++day;
if(day>monthLength){
day=1;
++month;
if(month>12){
month=1;
++year;
}
}
}
cout<<day<<' '<<month<<' '<<year<<'\n';
}