Problem H for Train 2
Задачу добавил: elena
Успешно сдано решений: 6
Problem H. Hot-keys
Author: A. Klenin
Input file: input.txt Time limit: 5 sec
Output file: output.txt Memory limit: 64 Mb
Statement
When designing dialog forms for interactive programs, it is important to assign hot-keys (known also as accelerator keys) to each dialog element, so as to facilitate keyboard input.
For better mnemonics, hot-keys are assigned based on the letters of dialog elements' captions, usually favoring letters near the beginning of caption. Manual hot-keys distribution can be tedious and error-prone, as one must be careful not to assign same letter to different elements.
Your program will be given a list of captions. It must assign unique hot-keys to as many captions of possible. Each assigned hot-key must be a letter from the corresponding caption.
For each hot-key, position is the leftmost occurrence of the hot-key letter in the corresponding caption. From all solutions with the same numbers of hot-keys, your program must choose the one with minimal sum of hot-key positions. If there is still more than one optimal solution, output any of them.
Input file format
Input file contains number of captions N followed by N lines with captions.
Output file format
Output file must contain N lines with the same captions as in input. In those captions which have hot-key assigned, leftmost occurrence of hot-key letter must be preceded with '&' (ASCII 38).
Constraints
1 <= N <= 10, all captions are from 1 to 10 characters in length and consist of small Latin letters.
Sample tests
Sample input 1
3
yes
no
cancel
Sample output 1
&yes
&no
&cancel
Sample input 2
4
abc
bca
acb
aaaa
Sample output 2
&abc
&bca
a&cb
aaaa