TopCoder problem "RemissiveSwaps" used in SRM 354 (Division I Level Two)



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.

 

Definition

    
Class:RemissiveSwaps
Method:findMaximum
Parameters:int
Returns:int
Method signature:int findMaximum(int N)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 1,000,000, inclusive.
 

Examples

0)
    
166
Returns: 560
The example from the problem statement.
1)
    
3499
Returns: 8832
The following sequence of operations is optimal: 3499 -> 8492 -> 8832.
2)
    
34199
Returns: 88220
The following sequence of operations is optimal: 34199 -> 84129 -> 88123 -> 88220.
3)
    
809070
Returns: 809070
No operations can increase the number.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7248

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10711&pm=7248

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Yarin , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Graph Theory