1028: SYH’s Easy 012 Problem
Memory Limit：256 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：9
Solved：1
Description
SYH has got a string with a length that is divisible by 3. The string only consists of ‘0’, ‘1’, ‘2’. You should blance the string that contains excatly |s|/3 ‘0’s, |s|/3 ‘1’s, |s|/3 ‘2’s. You should replace the minimum number of characters by only ‘0’, ‘1’, ‘2’. If there are multiple answers, output the smallest lexicographic answer.
Input
The first line conatins an integer T, means the number of test cases. For each test case, the first line contains a string s.
Output
For each test case ouput “Case: #x: s” in a single line. x is the test case number (starting from 1), and s is the balanced string which is your answer.
Sample Input Copy
2
121
111111Sample Output Copy
Case #1: 021
Case #2: 001122HINT
For the first sample, although “012”’s lexicographic order is smaller than “021”’s, “012” need to be replaced three elements which isn’t accord with the problem.
For the second sample, “112200” and “012012” also only need to be replaced four characters. However, “001122” is the smallest lexicographic order.
For the second sample, “112200” and “012012” also only need to be replaced four characters. However, “001122” is the smallest lexicographic order.
1 ≤ T ≤ 10, 3 ≤ |s| ≤ 3×105, 3 | |s|.