Confusing Five and Six
National Olympiad — National round (2019 season)
Submission name: suma.cpp
Problem summary
When copying two positive integers, Chris may confuse any occurrence of digit 5 with 6 and any 6 with 5. Find the minimum and maximum possible sums after such copying.
Input
Two positive integers A and B.
Output
The minimum possible sum followed by the maximum possible sum.
Constraints
1 ≤ A, B ≤ 1000000.
Worked example
An independently prepared example for this explanation.
Input
11 25
Output
36 37
Solution analysis
- Each occurrence of 5 or 6 can independently become the smaller digit 5 or the larger digit 6. All other digits are fixed.
- For the minimum, replace every 6 by 5 in both numbers. For the maximum, replace every 5 by 6. Parse the resulting digit strings and add the two minimized or maximized values.
- For 11 and 25, the smallest copied numbers are 11 and 25, totaling 36. The largest are 11 and 26, totaling 37. For 1430 and 4862, only the 6 changes, producing sums 6282 and 6292.
Why it works
Decreasing any independent digit decreases its number by a positive place value and cannot affect another digit’s choice. Hence choosing 5 at every ambiguous position minimizes each number and the total. Choosing 6 everywhere maximizes them by the same argument.
Watch out. Either digit may be copied correctly or confused; choices are independent. Print the minimum first, despite the introductory wording mentioning the maximum first.
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;
long long copiedValue(const string &digits, char chosen) {
long long value = 0;
for (char digit : digits) {
// Every ambiguous position independently chooses the same extremal digit.
if (digit == '5' || digit == '6') {
digit = chosen;
}
value = value * 10 + digit - '0';
}
return value;
}
int main() {
string a, b;
cin >> a >> b;
long long minimum = copiedValue(a, '5') + copiedValue(b, '5');
long long maximum = copiedValue(a, '6') + copiedValue(b, '6');
cout << minimum << ' ' << maximum << '\n';
}