Digits around a Triangle
National Olympiad — Municipal round (2018 season)
Submission name: maxtri.cpp
Problem summary
Three digits label the vertices of a triangle. Choose a starting vertex and traverse either clockwise or counterclockwise to form a three-digit number. Find the largest number obtainable.
Input
Three digits separated by spaces.
Output
The largest obtainable three-digit integer.
Constraints
Each input is a digit from 0 through 9; at least one is nonzero.
Worked example
An independently prepared example for this explanation.
Input
1 2 3
Output
321
Solution analysis
- A triangle has three possible starting vertices and two directions. These six choices cover every permutation of the three digit positions.
- Therefore sort the digits in decreasing order. The largest digit belongs in the hundreds position, the next in tens, and the smallest in units. At least one nonzero digit guarantees a three-digit result.
- For 1,2,3, the best choice reads 3,2,1 and forms 321. For 1,3,3 the repeated digits remain present, giving 331.
Why it works
Every ordering of three vertices is a legal traversal. If a smaller digit precedes a larger one, swapping them increases the decimal value, so descending order is the maximum legal ordering.
Watch out. Zeros are valid digits. Do not remove duplicate digits.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
array<int, 3> digits{};
for (int &digit : digits) {
cin >> digit;
}
// All six vertex permutations are legal triangle traversals.
sort(digits.begin(), digits.end());
cout << 100 * digits[2] + 10 * digits[1] + digits[0] << '\n';
}