Largest Card Number
Autumn Tournament (2017)
Submission name: maxcard.cpp
Problem summary
Four cards contain nonnegative integers. Arrange all four cards and concatenate their decimal representations to obtain the largest possible integer. At least one card is nonzero.
Input
Four integers c1, c2, c3, c4.
Output
The largest concatenated number.
Constraints
0 ≤ ci ≤ 9999; at least one ci is nonzero.
Worked example
First official statement sample.
Input
10 0 101 1005
Output
1011010050
Solution analysis
- Read each card as a string so concatenation means joining characters, rather than adding values.
- Sort the four strings and enumerate their distinct permutations. Every candidate has the same total number of digits, so lexicographic comparison selects the largest number. Only 24 permutations are possible.
- For 10, 0, 101, 1005, the order 101, 10, 1005, 0 produces 1011010050. Trying all orders also handles equal cards and prefix relationships.
Why it works
Every possible arrangement is a permutation visited by the loop. For equal-length decimal strings, their first differing digit determines their numeric order. The maintained maximum is therefore at least every arrangement and is itself achievable.
Watch out. Numeric descending order is insufficient: 101 must precede 10. Keep the answer as a string.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<string>
using namespace std;
int main(){
array<string,4>cards;
for(string&card:cards){
cin>>card;
}
sort(cards.begin(),cards.end());
string best;
do{
string candidate;
for(const string&card:cards){
candidate+=card;
}
// All candidates have the same length.
best=max(best,candidate);
}
while(next_permutation(cards.begin(),cards.end()));
cout<<best<<'\n';
}