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

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

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

E. Руины титанов: массовый контроль

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
— Кажется, мы в ловушке, — произнёс Альба.
— Это моя реплика, — ответил Сорен.
В этот раз друзья оказались в странной комнате, где, судя по всему, проводились эксперименты по массовому удалённому управлению объектами. Вдоль двух противоположных стен были выстроены в ряд n магических колец. Причём если в одном из рядов кольца были совершенно открыты и доступны, то весь второй ряд был закрыт непроницаемым силовым полем и подойти к нему было абсолютно невозможно.
Альба немного повернул одно из открытых колец, и все кольца, находившиеся в закрытом ряду, повернулись в разные стороны. Повернул второе — и они повернулись по-другому. Продолжив эксперименты, он смог выяснить, что при повороте любого из колец открытого ряда каждое из колец закрытого поворачивается на некоторый угол, кратный углу поворота исходного кольца. При этом направление поворота могло быть как по часовой стрелке, так и против неё.
Пока Альба исследовал кольца, Сорен пытался понять, как же им выбраться из комнаты. Всего в ней было две двери. В каждую из дверей упирался поток магической энергии, причём один из потоков проходил через открытый ряд колец, а другой — через закрытый.
Чтобы через ряд колец мог пройти энергетический поток, все они должны находиться в определённом положении. Если повернуть кольцо из этого положения на целое количество оборотов, оно всё ещё будет пропускать энергию, однако если повернуть лишь на часть оборота, то поток блокируется. Сорен понял, что когда-то потоки магической энергии поддерживали двери открытыми, однако теперь генератор, который их поддерживает, стал заметно слабее и на обе двери его не хватает. Поэтому нужно перекрыть один из потоков энергии, чтобы второй задействовал всю сохранившуюся мощность генератора, и открыл дверь.
Чтобы пройти дальше, вглубь подземелья, нужно открыть дверь, которая контролируется потоком, проходящим через ряд закрытых колец.

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

В первой строке целое n — количество колец в каждом из рядов (1 ≤ n ≤ 100). Далее в n строках по n целых чисел через пробел. i-е число в j-й строке Aij означает, что поворот i-го доступного кольца против часовой стрелки даёт Aij оборотов j-го из защищённых колец против часовой стрелки. Все Aij целые и не превосходят по модулю 100. Все кольца изначально находятся в том самом положении, при котором через них свободно проходит поток магической энергии.

Результат

Если друзьям не удастся пройти дальше, выведите единственную строку «Death». Иначе выведите единственную строку «Power of magic saves lives».

Пример

исходные данныерезультат
3
1 2 0
4 3 0
0 0 0
Power of magic saves lives

Замечания

Можно повернуть первое кольцо на 6/5 оборота по часовой стрелке, второе — на 8/5 оборота против часовой стрелки, а третье не поворачивать вовсе — поток заблокируется первым и вторым кольцами. В результате, в закрытом ряду первое кольцо повернётся на 2 оборота против часовой стрелки, второе — повращается и вернётся в исходное положение, а третье так и останется неподвижным.
Автор задачи: Александр Ипатов (подготовка - Дмитрий Иванков)
Источник задачи: NEERC 2012, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1914. Руины титанов: массовый контроль