Reach the Magic Spring
National Olympiad — Municipal round (2024 season)
Submission name: magiccure.cpp
Problem summary
A hero rows P meters toward a spring during a day and drifts R meters backward overnight, stopping as soon as the spring is reached. The spring is S meters away. Departure is Wednesday (weekday 3); find the number of days after departure when he arrives and that weekday. The departure day has index zero.
Input
S P R.
Output
Arrival day index after departure and weekday number (0 Sunday through 6 Saturday).
Constraints
100 ≤ S ≤ 10^8; 0 ≤ R < P ≤ 10^5.
Worked example
An independently prepared example for this explanation.
Input
1250 200 150
Output
21 3
Solution analysis
- He reaches P meters during departure day, before any backward drift. After d complete day-night cycles, his starting position is d·(P−R), and the next daytime trip can reach d·(P−R)+P.
- If S≤P, arrival occurs on departure day, index zero. Otherwise the smallest d with d·(P−R)≥S−P is ceil((S−P)/(P−R)). Compute it with integer ceiling division.
- For the sample, the remaining distance after the first day’s reach is 1050 and the net daily gain is 50, so d=21. Wednesday plus 21 days is still weekday 3.
Why it works
The hero arrives during day d exactly when its maximum daytime position reaches S. Earlier days have smaller maximum positions because P>R. The ceiling formula gives the first day satisfying this inequality, and weekday arithmetic reduces its offset modulo seven.
Watch out. Never subtract an overnight drift after reaching the spring. The sample uses days after departure: index 21 rather than a one-based count of 22 rowing days.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
long long distance, forward, backward;
cin >> distance >> forward >> backward;
long long day = 0;
if (distance > forward) {
long long gain = forward - backward;
// Day zero already reaches forward meters; only the remainder needs cycles.
day = (distance - forward + gain - 1) / gain;
}
cout << day << ' ' << (3 + day) % 7 << '\n';
}