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

Чемпионат Урала 2005 Тур II

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

E. Поймать Лару

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Кладбище имеет форму прямоугольника, в котором N рядов по M могил в каждом ряду. Кладбище окружено высокой стеной. Как вы уже знаете, Лара Крофт проникла на кладбище через подкоп с северо-западного угла с целью добыть спрятанное сокровище. Для этого она прорыла под кладбищем длинный подземный ход по такому правилу:
  1. Если дальше по ходу движения хода находилась целая могила, то Лара удлиняла ход и разоряла эту могилу.
  2. Если же впереди была стена кладбища или уже разорённая могила, то Лара поворачивала на 90 градусов вправо и продолжала своё подлое дело.
Лара только что нашла сокровище в могиле (rT, cT) и отправилась домой пить шампанское. Но тёмные силы решили устроить ей ловушку. Как только Лара дойдёт до могилы (rL, cL), запустится охранная сигнализация компании «LaraKiller», оживляющая скелетов в некоторых из разорённых могил. Все эти скелеты оживают одновременно, ровно через T секунд после включения сигнализации.
Лара понимает, что включилась сигнализация. Она может убежать с кладбища (если успеет) или спрятаться в одной из могил, которые она до этого разорила. Лара может бежать по своему подземному ходу (в сторону выхода или обратно) со скоростью не более одной могилы в секунду, поэтому за T секунд она может успеть спрятаться в любой из разорённых могил на расстоянии не более T от (rL, cL), считая по прорытому ходу.
Вы — главный программист «LaraKiller» и преданный борец с расхитителями гробниц. Вы считаете, что лишних скелетов оживлять ни к чему, поэтому хотите найти разорённые могилы, в которых может успеть спрятаться Лара.

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

В первой строке записаны целые числа N и M — размеры кладбища (2 ≤ N, M ≤ 100). Северо-западная могила имеет координаты (1, 1) а юго-восточная — (NM). Лара начала рыть свой ход с могилы (1, 1), двигаясь на восток, то есть к могиле (1, 2).
Во второй строке записаны целые числа rT и cT — координаты могилы с сокровищем. В третьей строке записаны целые числа rL и cL — координаты Лары в момент включения сигнализации. 1 ≤ rT, rLN; 1 ≤ cT, cLM. Гарантируется, что ход, прорытый от могилы (1, 1) до могилы (rTcT), проходит через могилу (rLcL).
В четвёртой строке записано целое число T — время оживления скелетов, в секундах (0 ≤ T ≤ 27000).

Результат

Выведите координаты всех могил, в которых может оказаться Лара через T секунд после включения сигнализации, координаты каждой могилы в отдельной строке. Могилы должны быть перечислены в том порядке, в котором они были разорены Ларой.

Пример

исходные данныерезультат
5 4
4 3
2 2
5
5 2
5 1
4 1
3 1
2 1
2 2
2 3
3 3
4 3

Замечания

На рисунке отмечены могилы, в которых Лара может успеть спрятаться.
Problem illustration
Автор задачи: Станислав Васильев
Источник задачи: IX Чемпионат Урала по спортивному программированию. Екатеринбург, УрГУ, 19-24 апреля 2005
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1364. Поймать Лару