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

H. Несколько строк

Задачу добавил: alef

Успешно сдано решений: 4

Ограничение по времени: 2 с на тест
Ограничение по памяти: 256 Мб


Во время посвящения в студенты первокурсников разделили на команды и устроили соревнование между этими командами. На первом этапе соревнования задача команд состоит в том, чтобы прочесть задание.

В этом не было бы ничего сложного, если бы командам выдали текстовый файл. Однако этот текстовый файл был N раз упакован в архив, притом каждый раз — с разным паролем. Каждая команда получила в свое распоряжение список всех паролей, которые были использованы при создании архивов. Более того, в качестве подсказки команды получили еще одну строку, сформированную следующим образом. Изначально строка была пустой. Когда файл был упакован в архив впервые, эта пустая строка была заменена паролем на этот архив. При каждой последующей архивации очередной пароль приписывался к этой строке справа.

— Да не нужна эта подсказка, и так можно попробовать подобрать. Этих паролей не больше двух десятков! — Харитон, попавший в одну команду с Феофаном, был просто уверен, что ему повезет если не на первый, то хотя бы на второй раз. Но архиватор вновь и вновь выдавал сообщение, что пароль неверен.

— Почему-то мне кажется, что быстрее написать программу, которая найдет нужную последовательность паролей, — возразил Феофан.

— Пиши! Посмотрим, кто быстрее! — Харитон продолжал экспериментировать, впечатывая очередной пароль в форму ввода.

Ваша задача — определить, в каком порядке использовались пароли при архивации. Если существует несколько вариантов ответа, выведите любой.

Формат входного файла input.txt

В первой строке входного файла содержится целое число N (2 ≤ N ≤ 20) — количество использованных при создании архива паролей. В каждой из следующих N строк содержится по одному паролю, состоящему из строчных латинских букв. Пароли считаются занумерованными в порядке их записи (т.е. в строке № i содержится пароль № (i - 1)).

Гарантируется, что все пароли являются непустыми строками.

В последней строке входного файла содержится подсказка — строка, которая была сформирована в процессе архивации. Длина строки не превышает 105 символов.

Формат выходного файла output.txt

В первой строке выведите N целых чисел через пробел — номера паролей в порядке появления их в строке-подсказке.

Примеры входных и выходных данных

Пример 1

Входные данные
3
aba
c
aba
abacaba
Выходные данные
1 2 3 
Пример 2

Входные данные
3
ac
aba
ab
abacaba
Выходные данные
3 1 2 

Сдать задачу

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