Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
725. Obfuscation
Динамическое программирование и запоминающие функцииСтруктуры данных
Олимпиадные задачи на английском языке
| 15/12/2007 | Тренировка (задачи ACM ICPC NWERC 2007) (H) |
| 04/07/2011 | Лето 2011 - дорешивание (12H) |
Ограничения: время – 6s/12s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
It is a well-known fact that if you mix up the letters of a word, while leaving the first and last letters in their places, words still remain readable. For example, the sentence "tihs snetncee mkaes prfecet sesne", makes perfect sense to most people.
If you remove all spaces from a sentence, it still remains perfectly readable, see for example: "thissentencemakesperfectsense", however if you combine these two things, first shuffling, then removing spaces, things get hard. The following sentence is harder to decypher: "tihssnetnceemkaesprfecetsesne".
You're given a sentence in the last form, together with a dictionary of valid words and are asked to decypher the text.
Input
On the first line one positive number: the number of testcases, at most 100. After that per testcase:
- One line with a string `s`: the sentence to decypher. The sentence consists of lowercase letters and has a length of at least 1 and at most 1000 characters.
- One line with an integer `n` with `1\ ≤\ n\ ≤\ 10\ 000`: the number of words in the dictionary.
- `n` lines with one word each. A word consists of lowercase letters and has a length of at least 1 and at most 100 characters. All the words are unique.
Output
Per testcase:
- One line with the decyphered sentence, if it is possible to uniquely decypher it. Otherwise "impossible" or "ambiguous", depending on which is the case.
Sample Input
3 tihssnetnceemkaesprfecetsesne 5 makes perfect sense sentence this hitehre 2 there hello hitehre 3 hi there three
Sample Output
this sentence makes perfect sense impossible ambiguous
