Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






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

Сдать задачу

Задать вопрос жюри по этой задаче