TheSwap
SRM 437 · 2009-03-24 · by Vasyl[alphacom]
Problem Statement
There is nothing more beautiful than just an integer number.
You are given an integer n. Write down n in decimal notation with no leading zeroes, and let M be the number of written digits. Perform the following operation exactly k times:
- Choose two different 1-based positions, i and j, such that 1 <= i < j <= M. Swap the digits at positions i and j. This swap must not cause the resulting number to have a leading zero, i.e., if the digit at position j is zero, then i must be strictly greater than 1.
Return the maximal possible number you can get at the end of this procedure. If it's not possible to perform k operations, return -1 instead.
Constraints
- n will be between 1 and 1,000,000, inclusive.
- k will be between 1 and 10, inclusive.
16375 1 Returns: 76315
The optimal way is to swap 1 and 7.
432 1 Returns: 423
In this case the result is less than the given number.
90 4 Returns: -1
We can't make even a single operation because it would cause the resulting number to have a leading zero.
5 2 Returns: -1
Here we can't choose two different positions for an operation.
91 3 Returns: 19
Submissions are judged against all 231 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheSwap with a public method int findMax(int n, int k) · 231 test cases · 2 s / 256 MB per case