Connection Status:
Competition Arena > PhoneNumbers

PhoneNumbers

TCO08 Qual 2 · 2008-01-21 · by ivan_metelsky

TCO08 Qual 2 · 2008-01-21 · by ivan_metelsky · Brute Force
Class Name: PhoneNumbers
Return Type: String
Method Name: bestNumber
Arg Types: (string)
Problem Statement

Problem Statement

You are given a String number containing the digits of a phone number. 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, and return the result as 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.

Notes

  • 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'.

Constraints

  • number will contain between 2 and 50 characters, inclusive.
  • Each character in number will be a digit ('0'-'9').
Examples
0)
"5088638"
Returns: "50-88-638"

There are three possible ways to divide this number into groups: 508-86-38 (quality 0), 50-886-38 (quality 1) and 50-88-638 (quality 2). The last option is the best one.

1)
"0123456789"
Returns: "01-23-45-67-89"

No matter how you divide this number, the quality will be 0. Choose the division that comes earliest lexicographically.

2)
"09"
Returns: "09"

With a 2-digit phone number, there is only one choice.

3)
"54545454545454545454"
Returns: "54-545-454-545-454-545-454"

The best way to divide this number is to create six 3-digit good groups and one 2-digit usual group. Put the 2-digit group at the beginning to achieve the lexicographically earliest result.

4)
"00110001011100010111"
Returns: "00-11-00-010-11-10-00-101-11"

Submissions are judged against all 155 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PhoneNumbers with a public method string bestNumber(string number) · 155 test cases · 2 s / 256 MB per case

Submitting as anonymous