MaxDiffBetweenCards
SRM 830 · 2022-05-27 · by misof
Problem Statement
A group of kids had N blank cards. Then, the following happened.
- Alice wrote a digit (0-9) onto each of the cards. At least one of the digits was non-zero.
- Bob arranged all N cards to form a valid non-negative integer. (The integer did not have any leading zeros.)
- Carol rearranged all N cards to form a valid non-negative integer. (Again, the integer did not have any leading zeros. Maybe it was the same integer as Bob's, maybe not.)
- Derek calculated the (non-negative) difference between Bob's and Carol's integer.
Calculate and return the largest value Derek could have obtained.
Constraints
- N will be between 1 and 17, inclusive.
1 Returns: 0
With just one card Bob and Carol both have to produce the same number, and Derek's difference will be zero.
2 Returns: 72
The biggest difference is produced if Alice writes the digits 9 and 1, and Bob and Carol arrange them to form the numbers 91 and 19, respectively.
4 Returns: 8811
Remember that some of the digits written by Alice may be zeros. The only requirement for her is that at least one of the digits must be non-zero. (This makes sure that Bob and Carol can always produce a valid integer.)
3 Returns: 801
5 Returns: 89001
Submissions are judged against all 17 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MaxDiffBetweenCards with a public method long long solve(int N) · 17 test cases · 2 s / 256 MB per case