Problem 4

All submissions for this problem are available.
You are given a String number of length N containing the digits of a phone number.
Each character in number will be a digit ('0''9').
To help you memorize the number, you want to divide it into groups of contiguous digits.
Each group must contain exactly 2 or 3 digits. There are three kinds of groups:
Excellent: A group that contains only the same digits. For example, 000 or 77.
Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166.
Usual: A group in which all the digits are distinct. For example, 123 or 90.
The quality of a group assignment is defined as 2 * (number of excellent groups) + (number of good groups).
Divide the number into groups such that the quality is maximized,
where each pair of consecutive groups is separated by a dash ('').
If there are multiple ways to do this, return the one among them that results in the lexicographically earliest String.
A String A comes before a String B lexicographically if A is a proper prefix of B,
or if A has a smaller character
at the first position where the strings differ.
When comparing the characters, refer to the following list of characters
in ascending order:
'', '0', '1', ..., '9'.
Input
The first line of input will consist of the number of test cases t(1<= t <=20) followed by t test cases.
Each test case will consist of a String of length N(2<=N<=50) containing the digits of a number.
Output
Output is a String, where each pair of consecutive groups is separated by a dash ('').
If there are multiple ways to do this, return the one among them that results in the lexicographically earliest String.
Examples
Input 5 5088638 0123456789 09 54545454545454545454 00110001011100010111 OutPut 5088638 0123456789 09 54545454545454545454 00110001011100010111
Author:  admin 
Tags  admin 
Date Added:  21092009 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 