Connection Status:
Competition Arena > CalcButton

CalcButton

SRM 246 · 2005-06-09 · by Andrew_Lazarev

SRM 246 · 2005-06-09 · by Andrew_Lazarev · Brute Force
Class Name: CalcButton
Return Type: String
Method Name: getDigits
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are developing a new software calculator. You decided to add a new feature - the three-digit button. Clicking on this button will add three digits into the edit field. This feature is for fast typing of common digit combinations. The problem is to figure out which digits should be placed on this button. You have prepared some statistical data - a long sequence of digits. You have decided that the button will be chosen to minimize the quantity of clicking required for typing this sequence.

You will be given a String[] sequence. The data is divided into several rows only for convenience. You can assume that this is a solid array (i.e. the first character in the i-th row is directly after the last character in the (i-1)-th row). You should return a three-character String containing the digits on the button. If there are several solutions you should return the one which appears first lexicographically.

Constraints

  • sequence will have between 1 and 50 elements, inclusive.
  • Each element of sequence will contain between 1 and 50 characters, inclusive.
  • Each element of sequence will contain only digits ('0'-'9').
Examples
0)
{"100002000"}
Returns: "000"

We can type the sequence in 5 clicks (the extra button is used twice)

1)
{"777777777"}
Returns: "777"

We can type the entire sequence in 3 clicks

2)
{"6503","210"}
Returns: "032"

A sequence can be divided into several rows.

3)
{"0993034","6","4137","45959935","25939","93993","0","9358333"}
Returns: "993"
4)
{"142475555","008","8763","698589","74","4697753","5706650897","1","767152","626182814","32721590","8071031799","7","54513471","843074","00429","37800","5271807","954937180","0646","70304395","957","6","76"}
Returns: "718"

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

Coding Area

Language: C++17 · define a public class CalcButton with a public method string getDigits(vector<string> sequence) · 132 test cases · 2 s / 256 MB per case

Submitting as anonymous