Trees Around a Garden
Autumn Tournament (2009)
Submission name: garden.cpp
Problem summary
A rectangular garden has sides A and B. Starting at one corner, walk clockwise around its boundary in steps of length P, planting at every new reached position until no new position can be reached. Find the number of planted trees and the total distance needed to whitewash them: for each tree start at the original corner, take the shorter boundary route to that tree, and return to the corner.
Input
Three integers A, B and P.
Output
The number of trees and the total whitewashing travel distance.
Constraints
1 ≤ A,B ≤ 100; 1 ≤ P ≤ 2A+2B.
Worked example
Original statement sample.
Input
6 4 5
Output
4 40
Solution analysis
- Unroll the boundary into positions 0 through perimeter−1, with the original corner at 0. One planting step changes position to (position+P) modulo perimeter. Keep a visited flag for every boundary position and stop upon reaching a visited one.
- A tree at position position is at boundary distance min(position,perimeter−position) from the corner. Whitewashing requires a separate round trip, so add twice this distance for each newly visited position. The original tree contributes zero.
- For A=6, B=4 and P=5, the perimeter is 20 and the visited positions are 0,5,10,15. The one-way shortest distances are 0,5,10,5, hence 4 trees and total travel 2×20=40.
- The planting sequence has perimeter/gcd(perimeter,P) distinct positions, but the perimeter is at most 400, so direct simulation is especially simple and also computes the travel sum without a separate formula.
Why it works
Modulo arithmetic describes the exact boundary position after each planting step. A repeated position repeats the entire future sequence, so no unvisited position can follow it. The loop therefore visits every planted tree exactly once. The shorter of the two boundary routes is its minimum permitted one-way distance, and doubling and summing gives all required round trips.
Watch out. Use boundary distance, not straight-line distance through the garden. Include the final return to the barrel. Planting steps can require multiple laps; do not stop after just one lap.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int a,b,step;
cin>>a>>b>>step;
int perimeter=2*(a+b);
vector<bool>visited(perimeter,false);
int position=0;
int trees=0;
int distance=0;
while(!visited[position]){
visited[position]=true;
trees++;
// Each tree needs its own shortest boundary round trip.
distance+=2*min(position,perimeter-position);
position=(position+step)%perimeter;
}
cout<<trees<<' '<<distance<<'\n';
}