Rotating Digit Cards
National Olympiad — Municipal round (2017 season)
Submission name: chislo.cpp
Problem summary
Two cards each show a digit from 1, 6, 8, 9. Rotating a card keeps 1 and 8 unchanged but swaps 6 and 9. You may rotate and reorder the cards. Find the greatest two-digit number possible.
Source clarification. The input prose separates the two digits with a space, but the official sample is 16. Character extraction accepts either representation.
Input
The two digit characters, with or without separating whitespace.
Output
The maximum two-digit number.
Constraints
Each digit is one of 1, 6, 8, 9.
Worked example
An independently prepared example for this explanation.
Input
16
Output
91
Solution analysis
- Each card can be improved independently: a 6 may be rotated into a 9, while 1, 8 and 9 are already at their maximum possible values.
- After replacing each 6 by 9, put the larger digit in the tens position. A one-unit increase in the tens place is worth ten, so this order is always at least as good as the reverse.
- The sample cards 1 and 6 become 1 and 9 after rotation. Putting 9 first gives 91, which exceeds 19 and every arrangement using 6.
Why it works
Replacing either card by a larger available digit never decreases a number regardless of its position, so both cards can first be maximized. For resulting digits a ≥ b, the difference between 10a + b and 10b + a is 9(a − b) ≥ 0. Thus descending order is optimal.
Watch out. Read digits as characters: the official example writes 16 without a space despite the input prose mentioning a separator.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <utility>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
char a, b;
cin >> a >> b;
if (a == '6') {
a = '9';
}
if (b == '6') {
b = '9';
}
// Once each digit is maximized, the larger belongs in the tens place.
if (a < b) {
swap(a, b);
}
cout << a << b << '\n';
return 0;
}