Connection Status:
Competition Arena > MnemonicMemory

MnemonicMemory

SRM 357 · 2007-07-12 · by ValD

SRM 357 · 2007-07-12 · by ValD · Brute Force, Simple Search, Iteration, String Parsing
Class Name: MnemonicMemory
Return Type: String
Method Name: getPhrase
Arg Types: (string, vector<string>)
Problem Statement

Problem Statement

It is often helpful to have a mnemonic phrase handy for a math test. For example, the number 25735 can be remembered as "is there anybody out there". If we count the number of characters in every word, we would get the sequence 2, 5, 7, 3, 5, which represents the original number!

Unfortunately for you, your professor likes to make the students memorize random numbers and then test them. To beat the system, your plan is to come up with mnemonic phrases that will represent the numbers you must memorize.

You are given a String number and a String[] dictionary. Return a single space delimited list of words, where each word is an element of dictionary, and no element of dictionary is used more than once. The phrase must contain exactly n words, where n is the number of digits in the number, and the length of the i-th word must be equal to the i-th digit of the number for all i. If more than one phrase is possible, return the one that comes first alphabetically (in other words, if you have several words of the same length, you should use them in alphabetical order).

Constraints

  • dictionary will contain between 1 and 50 elements, inclusive.
  • Each element of dictionary will contain between 1 and 9 characters, inclusive.
  • Each element of dictionary will contain only lowercase letters ('a'-'z').
  • number will contain between 1 and 50 characters, inclusive.
  • number will contain only digits between '1' and '9', inclusive.
  • There will always be a possible solution with the given dictionary.
Examples
0)
"25735"
{"is", "there", "anybody", "out", "there"}
Returns: "is there anybody out there"

The example from the problem statement.

1)
"31415926"
{"may", "i", "have", "a", "large", "container", "of", "coffee"}
Returns: "may a have i large container of coffee"

Make sure you use words of the same length in alphabetical order.

2)
"1212"
{"a", "aa", "a", "aa"}
Returns: "a aa a aa"
3)
"11111111122"
{"a", "b", "d", "c", "a", "e", "f", "z", "zz", "za", "az", "e"}
Returns: "a a b c d e e f z az za"
4)
"2222"
{"ab", "cd", "ef", "a", "b", "ab"}
Returns: "ab ab cd ef"

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

Coding Area

Language: C++17 · define a public class MnemonicMemory with a public method string getPhrase(string number, vector<string> dictionary) · 45 test cases · 2 s / 256 MB per case

Submitting as anonymous