Задачи
Optimal Keypad
Optimal Keypad
\includegraphics{https://static.e-olymp.com/content/85/8538150ed33e7cfbc3d3c2f159c91ef4769f5e56.jpg}
Optimus Mobiles produces mobile phones that support SMS messages. The Mobiles have a keypad of \textbf{12} keys, numbered \textbf{1} to \textbf{12}. There is a character string assigned to each key. To type in the \textbf{n}^th character in the character string of a particular key, one should press the key \textbf{n} times. Optimus Mobiles wishes to solve the problem of assigning character strings to the keys such that for typing a random text out of a dictionary of common words, the average typing effort (i.e. the average number of keystrokes) is minimal.
To be more precise, consider a set of characters \{\textbf{a}, \textbf{b}, \textbf{c}, …, \textbf{z}, \textbf{+}, \textbf{*}, \textbf{/}, \textbf{?}\} printed on a label tape as in \textit{\textbf{Fig. 2}}. We want to cut the tape into \textbf{12} pieces each containing one or more characters. The \textbf{12} labels are numbered \textbf{1} to \textbf{12} from left to right and will be assigned to the keypad keys in that order.
\includegraphics{https://static.e-olymp.com/content/13/13ac15cf9206c6af2f63db8dec58b97dcb36bd09.jpg}
\textit{\textbf{Figure 2}}
You are to write a program to find the \textbf{11} cutting positions for a given dictionary of common words. The cutting positions should minimize the average number of keystrokes over all common words in the dictionary. Your output should be a string of \textbf{11} characters, where character \textbf{i} in this string is the first character of the \textbf{(i+1)}^th label.
\InputFile
The first line contains a single integer \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10}), the number of test cases. Each test case starts with a line, containing an integer \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{10000}), the number of common words in the test case. In each \textbf{M} subsequent line, there is a common word. Each common word contains at most \textbf{30} characters from the alphabet \{\textbf{a}, \textbf{b}, \textbf{c}, …, \textbf{z}, \textbf{+}, \textbf{*}, \textbf{/},\textbf{?}\}.
\OutputFile
The output contains one line per test case containing an optimal cut string. Obviously, there may be more than a single optimal cut string, so print the optimal cut string which is the smallest one in lexicographic order.
Входные данные #1
5 2 hi ok 5 hello bye how when who 4 abcd befg chijklm dopqrst 10 ? / * + u v w x y z 7202 abandonment abarticulation abbreviation abdominoscopy abecedarian abecedarium abelmoschus aberrometer abiogenesis ablactation abnormality abolitionism abomination abortifacient abortionist aboveground abovestairs abra?dabra abranchiate abridgement absenteeism absentminded abstraction abstractionism abstractive a?demi?ls a?demician a?demicism a?n+ocephala a?n+osisnigri?ns a?rpellous a?talectic a?tama+esia a?ulescent accelerando acceleration accelerator accelerometer acceptability acceptation accessariness accessibility accessorial accessories acciac?tura accidentalism acclamation acclimatation acclimatization acclimatize accommodate accommodating accommodation accommodator accompaniment accompanist accompli*ed accompli*ment accordingly accouchement accoucheuse accountability accountable accountancy accouterment acculturate accumulation accumulative accumulator acetifi?tion acetomorphine acetylatio ...
Выходные данные #1
bcdefghijko bcdefhlnowy bcdefhjloqs buvwxyz+*/? cegilnorsty