Beautiful Phone Numbers
InterviewTime limit2sMemory limit1024 MB
Given a 7-digit phone number, split the digits with hyphens into groups of 2 to 4 digits so that the total pattern-based beauty score is maximized, and print the best split with its score.
- Level
Medium6 of 10
- Topics
- Dynamic programming, String, Implementation, Brute force
- Solved
- No attempts yet
Problem
You have probably noticed that many companies use <> phone numbers in their advertising, ones that are easy for potential clients to remember. But what if your company's number is nothing special? You can look at it more closely. Perhaps rearranging the digits in some way will make the number much more beautiful. For example, if your company's number is 872-73-33, you can make it more beautiful by rearranging the digits as 8727-333.
We introduce the following measure of the beauty of a split of a number. We split the number with hyphens into groups of 2 to 4 digits. The beauty of the split is the sum of the scores each group contributes. These scores are computed using the following table.
In this table, the symbols <>, <>, <> denote distinct digits. For example, the groups <<223>> and <<667>> match the pattern <>, but <<123>> and <<888>> do not.
Using this scoring system, find the most beautiful split of the given number.
Input
The input file contains a single line of 7 digits, the given phone number.
Output
In the first line of the output file, print the most beautiful split of the number, and in the second line, its beauty value.
If several splits have the maximum beauty value, print any one of them.