Ruler
Autumn Tournament (2007)
Submission name: ruler.cpp
Problem summary
Three wooden strips lie on a ruler marked from 0 to 100000 cm. For each strip you know its length and the mark at its right end. Find the smallest starting mark.
Input
Three lines, each containing a strip length and its right endpoint.
Output
The smallest starting mark.
Constraints
Each supplied integer is between 1 and 100000; strips lie on the ruler.
Worked example
Original statement sample.
Input
3 9 8 12 6 15
Output
4
Solution analysis
- A strip ending at end with length length begins at end − length. Compute this for each of the three strips.
- Keep the smallest start seen so far. A running minimum avoids storing the strips.
- The sample starts are 9 − 3 = 6, 12 − 8 = 4, and 15 − 6 = 9. Their minimum is 4.
Why it works
Each computed difference is precisely that strip’s starting mark. Taking the minimum of all three therefore returns the start nearest to zero.
Complexity: O(1) time and O(1) extra space.
Watch out. The input gives length first and endpoint second. Do not take the minimum endpoint.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int closest=100000;
for(int strip=0;strip<3;strip++){
int length,endpoint;
cin>>length>>endpoint;
// A strip extends its length to the left of its endpoint.
closest=min(closest,endpoint-length);
}
cout<<closest<<'\n';
}