ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2013, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Секретный модуль

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Палпатин: Поднимись, друг мой.
Дарт Вейдер: «Звезда Смерти» будет готова к сроку.
Палпатин: Ты хорошо потрудился, лорд Вейдер.
Космическая станция Звезда Смерти была создана для контроля целой галактики. Эта станция была оснащена мощнейшим оружием и могла нести на своём борту тысячи истребителей. Чтобы повстанцы не могли подобраться к Звезде Смерти, был принят ряд мер предосторожности. В частности, все приближающиеся к станции истребители подлежали строгому осмотру. Контроль за соблюдением пропускного режима был возложен на специальный модуль, считывающий и проверяющий бортовой номер корабля.
Номер истребителя является целым неотрицательным числом и считывается в порядке слева направо. Он должен одинаково обрабатываться при любом количестве ведущих нулей. Проверяющий модуль представляет собой конечный детерминированный автомат с n состояниями. Изначально автомат находится в первом состоянии и осуществляет проверку бортового номера следующим образом. Считав очередную цифру, автомат меняет своё состояние по некоторому правилу, определяемому текущим состоянием и обрабатываемой цифрой. Если, проанализировав весь бортовой номер, автомат оказывается в терминальном состоянии, то станция пропускает истребитель. Иначе отдаётся приказ на уничтожение. Истребители без указанного номера также подвергаются уничтожению, поэтому первое состояние автомата не является терминальным.
Такая схема прекрасно работала до тех пор, пока повстанцы не уничтожили станцию. Проектировщики новой Звезды Смерти решили использовать аналогичную технологию проверки бортовых номеров. Но повстанцам уже известны номера многих вражеских кораблей, поэтому, в целях повышения безопасности, номера всех имперских истребителей были увеличены на некоторое число k.
Вашей задачей является проектирование специального модуля для новой Звезды Смерти. Этот модуль должен принимать решение пропустить истребитель в том и только том случае, когда его номер является новым номером одного из имперских истребителей.

Исходные данные

В первой строке входных данных находится целое число k (1 ≤ k ≤ 8). Далее следует описание автомата. В первой строке описания задаётся количество состояний автомата n (1 ≤ n ≤ 100). Во второй строке описания находится n чисел ti (ti ∈ {0, 1}). ti = 1, если i-ое состояние является терминальным и ti = 0 в противном случае. В i-ой из следующих n строк находится описание очередного состояния, представляющее собой 10 чисел из диапазона от 1 до n. Эти числа соответствуют номерам состояний, в которые перейдёт автомат, прочитав из состояния i цифру 0, 1, …, 9 соответственно.

Результат

Если не существует автомата, подходящего для новой Звезды Смерти, выведите «Impossible». Если автомат существует, выведите «Success», а затем описание автомата в том же формате, что и на входе. В вашем автомате должно быть не более 25 600 состояний. Гарантируется, что если существует подходящий автомат, то существует и автомат, удовлетворяющий указанному ограничению.

Пример

исходные данныерезультат
3
4
0 0 1 0
1 2 4 4 4 4 4 4 4 4
4 2 4 4 4 4 4 4 3 4
4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4
Success
5
0 0 0 0 1
1 2 3 4 4 4 4 4 4 4
4 2 3 4 4 4 4 4 4 4
4 5 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4
Автор задачи: Денис Дублённых (подготовка — Евгений Курпилянский)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1999. Секретный модуль