Monkey Reaches the Top
National Olympiad — Municipal round (2014 season)
Submission name: monkey.cpp
Problem summary
A monkey starts climbing on date D M G. Each day it climbs K metres; each night before reaching the top it slips X metres. Find the date it first reaches a tree’s height N.
Input
Six integers D M G N K X.
Output
The finishing date as day month year, separated by spaces.
Constraints
1 ≤ D ≤ 31; 1 ≤ M ≤ 12; 1900 ≤ G ≤ 2020; 4 ≤ N ≤ 20; 2 ≤ K ≤ 15; 1 ≤ X ≤ 14; X<K≤N. The starting date is valid.
Worked example
An independently prepared example for this explanation.
Input
6 9 2012 15 5 4
Output
16 9 2012
Solution analysis
- At each day’s start, test whether one more climb reaches the top. If it does, finish on that date without applying a night slip. Otherwise add the net daily progress K−X and move the date forward one day.
- To advance the date, use the month length, with February 29 in years divisible by 400 or divisible by 4 but not 100. After the last day, advance month and possibly year.
- The sample gains one metre after each unfinished day. On September 16 the monkey starts at height 10 and climbs to 15, so it finishes that day.
Why it works
At every iteration, height and date describe the start of the next climbing day. A successful climb is immediately detected. An unsuccessful climb followed by the slip advances height by K−X, and date advancement preserves the invariant. Positive net progress guarantees termination at the first successful day.
Watch out. Never slip after reaching the top. The starting day counts as the first climb. Century years such as 1900 are not leap years.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
bool leapYear(int year) {
return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
}
int main() {
int day, month, year, tree, climb, slip;
cin >> day >> month >> year >> tree >> climb >> slip;
int height = 0;
const int monthDays[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// A successful daytime climb finishes before any night slip.
while (height + climb < tree) {
height += climb - slip;
int length = monthDays[month];
if (month == 2 && leapYear(year)) {
length++;
}
day++;
if (day > length) {
day = 1;
month++;
if (month > 12) {
month = 1;
year++;
}
}
}
cout << day << ' ' << month << ' ' << year << '\n';
}