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

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

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

K. Руины титанов: бесконечная сила магии

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
— Похоже, наши усилия не были напрасны, — произнёс Альба, оторвавшись от изучения древнего тома. — Здесь описан способ накопления чудовищного количества магической энергии. И ведь идея сама по себе настолько проста, что даже удивительно, что никто до неё не додумался раньше. Ведь проблема в чём — магическая энергия сама по себе крайне нестабильна и удержать её в одном месте весьма непросто. Но если пустить её вдоль замкнутого контура, то никуда она из него не денется. Надо только подобрать правильную длину контура, иначе из-за взаимодействия на разных частях она начнёт понемногу угасать. А так её можно вливать в этот контур в сколь угодно больших количествах. И если затем этот контур разорвать, то можно получить магический всплеск недостижимой ранее мощи. Только представь, какой это рывок для военной магии!
— Так то оно так, только длина контура должна быть достаточно большой. Не будешь же с такой махиной на поле боя таскаться.
— Это тоже не проблема. Форма контура может быть достаточно произвольной. Если постараться, то можно сделать достаточно компактную конструкцию контура. Собственно, видишь вон то устройство? Нам требуется только настроить его.
Устройство представляло собой квадратную решётку размера n × n узлов. В каждом из узлов была закреплена призма, которая в зависимости от её поворота либо пропускала поток магической энергии сквозь себя напрямую, либо поворачивала его на 90°. Теперь друзьям нужно было повернуть L призм так, чтобы через них можно было бы запустить циклический поток магической энергии длины L.

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

На входе даны два целых числа — n и L (2 ≤ n ≤ 100; 4 ≤ L ≤ 20 000).

Результат

Если цикл нужной длины организовать невозможно, выведите «Unsuitable device». В противном случае в первой строке выведите «Overwhelming power of magic». В следующих L строках выведите по два числа от 1 до n — координаты узлов решётки, через которые должна проходить энергия. Расстояния между двумя последовательными узлами, а также между первым и последним должно быть равно 1. Ни через какой узел энергия не должна проходить дважды, иначе возможны непредсказуемые и, скорее всего, смертельные эффекты.

Примеры

исходные данныерезультат
2 6
Unsuitable device
3 6
Overwhelming power of magic
1 1
2 1
3 1
3 2
2 2
1 2
Автор задачи: Алексей Самсонов (подготовка - Дмитрий Иванков)
Источник задачи: NEERC 2012, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1920. Руины титанов: бесконечная сила магии