RemissiveSwaps
SRM 354 · 2007-06-14 · by Andrew_Lazarev
Problem Statement
You are given an integer N, and you are allowed to perform the following operation: take two nonzero digits of N, decrease each of them by one and swap the resulting digits. For example, if N is 166, you can reach the following numbers in one operation: 506 (swap '1' and the first '6'), 155 (swap the '6's) and 560 (swap '1' and the last '6'). You are allowed to perform the operation zero or more times consecutively. Return the largest number you can reach.
Constraints
- N will be between 1 and 1,000,000, inclusive.
166 Returns: 560
The example from the problem statement.
3499 Returns: 8832
The following sequence of operations is optimal: 3499 -> 8492 -> 8832.
34199 Returns: 88220
The following sequence of operations is optimal: 34199 -> 84129 -> 88123 -> 88220.
809070 Returns: 809070
No operations can increase the number.
1 Returns: 1
Submissions are judged against all 161 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RemissiveSwaps with a public method int findMaximum(int N) · 161 test cases · 2 s / 256 MB per case