Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
791. Bonus Word
Олимпиадные задачи на английском языке| 08/02/2008 | Тренировка (задачи Benelux APC preliminary 2007) (B) |
| 11/07/2013 | Лето 2013-8 (B) |
Ограничения: время – 5s/10s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Lingo is a once popular game show where the contestants have to guess words. In the
original version the contestants would have to guess a five-letter word each round.
In between the rounds of regular word guessing, the contestants can win a bonus prize if
they can guess a ten-letter word. The ten-letter word is displayed with the letters permuted.
Some letters are colored indicating that they are displayed in the right position. Since
there are not that many ten-letter words, it happens frequently that the word is actually
a compound: a word constructed by concatenating two shorter words. In this problem we
assume that the ten-letter word is always of this form.
Given a dictionary and a sequence of ten letters, you must calculate the possible solutions
to the ten-letter word game. Two solutions are considered different if they are constructed
from different parts, even if their concatenation is the same. This is illustrated by the the
second sample case.
Input
On the first line an integer `t` (`1\ ≤\ t\ ≤\ 100`): the number of test cases. Then for each test
case:
- One line with an integer `n` (`1\ ≤\ n\ ≤\ 200`): the number of words in the dictionary.
- `n` lines with a single word in the dictionary. Each word is between 1 and 9 (inclusive) characters long and consists of only lowercase letters.
- One line with an integer `q` (`1\ ≤\ q\ ≤\ 100`): the number of queries.
- `q` lines with a single query string. Each query is exactly 10 characters long and will consist of uppercase and lowercase letters. Lowercase letters are in the right position and uppercase letters may be in the wrong position.
All words in the dictionary for a single test case are distinct.
Output
For each test case, output for each query:
- One line with an integer `s`: the number of solutions.
- `min(1000,\ s)` lines, each a solution formatted as two dictionary words separated by a hyphen (-).
The solutions to a single query must be ordered lexicographically. If the number of solutions
exceeds 1000, then only output the first 1000 solutions.
Notes
If `s` and `t` are strings of equal length and `s_i` denotes the `i`th character of `s`, then `s` precedes
`t` lexicographically if for some `i`: `s_i\ <\ t_i` and `s_j` = `t_j` for all `j\ <\ i`.
Sample input
2 5 gunner integral relating tail un 4 TAILGUNNER unINTEGRAL UNrelating IMPOSSIBLE 3 aaaa aaaaa aaaaaa 1 AAAAAAAAAA
Sample output
6 gunner-tail integral-un relating-un tail-gunner un-integral un-relating 2 un-integral un-relating 1 un-relating 0 3 aaaa-aaaaaa aaaaa-aaaaa aaaaaa-aaaa
