Burning Sticks
Autumn Tournament (2013)
Submission name: stick.cpp
Problem summary
Three sticks lie on a numbered line. Fire spreads between sticks that overlap or touch at an endpoint. Find the minimum number of sticks that must be lit so all burn, and the lengths of the shortest and longest sticks.
Input
Three lines, each giving a stick’s left and right endpoints. Sticks are ordered by their left endpoints.
Output
First print the minimum number to light. On the next line print the minimum and maximum lengths.
Constraints
The numbered line is no longer than 100 centimetres. Each pair gives a stick’s left and right endpoints.
Worked example
Original statement sample, translated without changing its numeric data.
Input
2 4 3 6 7 8
Output
2 1 3
Solution analysis
- Sticks connected by overlap or endpoint contact form a group that burns after any one of its sticks is lit. Different groups need separate initial flames.
- Scan from left to right, maintaining the rightmost endpoint of the current group. A new stick starts a new group only when its left endpoint is strictly greater than that endpoint. Otherwise extend the endpoint if necessary. Track each length as right − left.
- In the sample [2,4] and [3,6] overlap and form one group. [7,8] is separate, so two flames are needed. The lengths are 2, 3 and 1, giving 1 and 3.
Why it works
Before each step, the maintained endpoint is the farthest point reached by the current connected group. A stick beginning at or before it touches that group; a stick beginning later is separated by a gap and starts another. Thus the scan counts exactly the connected groups. Each group needs at least one lit stick and one is sufficient, proving minimality. Computing each endpoint difference and taking extrema gives the requested lengths.
Watch out. Touching endpoints connect; endpoints one centimetre apart do not. Keep the maximum right endpoint of the whole group, including when one stick contains another. Length is right − left, without adding one.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int groups=0;
int groupRight=-1;
int shortest=101;
int longest=0;
for(int i=0;i<3;i++){
int left,right;
cin>>left>>right;
if(i==0||left>groupRight){
groups++;
groupRight=right;
}
else{
// A containing stick may already extend farther.
groupRight=max(groupRight,right);
}
int length=right-left;
shortest=min(shortest,length);
longest=max(longest,length);
}
cout<<groups<<'\n';
cout<<shortest<<' '<<longest<<'\n';
}