DigitsSwap
SRM 436 · 2009-03-11 · by Gluk
SRM 436 · 2009-03-11 · by Gluk · Simple Math, Simple Search, Iteration
Problem Statement
Problem Statement
You are given two positive integers, x and y, whose decimal representations contain the same number of digits. A digit-swap operation for an index i swaps the digits at the i-th positions in x and y. After exactly swaps digit-swap operations, what is the maximal possible value of x*y? Return the String representation of this maximal product with no leading zeroes.
Constraints
- x and y will each contain between 1 and 50 characters, inclusive.
- x and y will contain only decimal digits ('0' to '9'), and will not start with a '0'.
- x and y will contain the same number of characters.
- swaps will be between 0 and 1,000,000,000, inclusive.
Examples
0)
"123" "321" 2 Returns: "39483"
You can transform the numbers to "123", "321" (making two swaps at the same position) or to "321", "123" (making swaps at positions 0 and 2) to produce the product 39483.
1)
"4531" "1332" 0 Returns: "6035292"
You are not allowed to make swaps, so the answer is just x * y.
2)
"13425" "87694" 99 Returns: "1476187680"
The optimal answer is 17695 * 83424.
3)
"2872876342876443222" "2309482482304823423" 5 Returns: "6669566046086333877050194232995188906"
4)
"940948" "124551" 4893846 Returns: "133434353148"
Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DigitsSwap with a public method string maximalProduct(string x, string y, int swaps) · 116 test cases · 2 s / 256 MB per case