eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Электронная охота

Электронная охота

С древних времен одним из занятий человека была охота. Сначала это было средство получения пищи, позднее оно превратилось в развлечение, у которого стало появляться все больше противников -- защитников животных. Чтобы найти компромисс между любителями охоты и защитниками животным была разработана "электронная охота на кабана". Охота выполняется на заранее отведенной прямоугольной площадке, разбитой на маленькие квадраты, часть которых засажена густым кустарником. Таким образом, площадка для охоты представляет собой "живой" лабиринт. В некоторый квадрат площадки, не засаженный кустарником, выпускается "кабан" -- электронный робот, запрограммированный на выполнение определенного числа шагов. Шагом считается переход "кабана" из текущего квадрата в один из соседних, не засаженных кустарником (по горизонтали, вертикали или диагоналям), либо отсутствие движения (т.е. на некотором шаге "кабан" может остаться на месте). Вероятность перехода "кабана" из текущего квадрата в любой из соседних, а также отсутствия движения, одинакова. После выполнения "кабаном" заданного количества шагов охотник, снабженный лазерной винтовкой, выбирает квадрат, не засаженный кустарником, из которого он будет проводить выстрел. Выстрел считается удачным, если из квадрата, выбранного охотником, по вертикали, горизонтали, либо диагоналям виден "кабан", или кабан находится в квадрате, выбранном охотником. При этом, если охотник и "кабан" расположены на одной линии, но между ними находится квадрат с кустарником, то "кабан" считается невидимым. Помогите охотнику найти квадрат, вероятность удачного выстрела из которого наибольшая. \InputFile Первая строка содержит два целых числа \textbf{nX} и \textbf{nY}, разделенных пробелом -- размер площадки по горизонтали и вертикали, соответственно (\textbf{1} ≤ \textbf{nX}, \textbf{nY} ≤ \textbf{100}). Вторая строка содержит целое число \textbf{K} -- количество квадратов, засаженных кустарником (\textbf{0} ≤ \textbf{K} < \textbf{nX}*\textbf{nY}). Следующие \textbf{K} строк содержат по два целых числа \textbf{X} и \textbf{Y} -- координаты одного из квадратов, засаженных кустарником (\textbf{1} ≤ \textbf{X} ≤ \textbf{nX}, 1 ≤ \textbf{Y} ≤ \textbf{nY}). Гарантируется, что все пары (\textbf{X}, \textbf{Y}) уникальны. Последняя строка содержит три целых числа \textbf{kX}, \textbf{kY} и \textbf{N}, разделенных пробелами -- начальные координаты "кабана" и количество его шагов (\textbf{1} ≤ \textbf{kX} ≤ \textbf{nX}, \textbf{1} ≤ \textbf{kY} ≤ \textbf{nY}, \textbf{1} ≤ \textbf{N} ≤ \textbf{50}). \OutputFile Выходной файл должен содержать два целых числа \textbf{oX} и \textbf{oY}, разделенных пробелом -- координаты квадрата, имеющего наибольшую вероятность удачного выстрела. Если таких квадратов несколько, то выводится тот, координата \textbf{X} которого наименьшая. В случае если и таких квадратов несколько, то выводятся координаты квадрата с наименьшей координатой \textbf{Y}. \textit{\textbf{Два значения вероятностей считаются одинаковыми, если разница между ними не превышает}} \textbf{10^\{‑6\}}.
Лимит времени 0.4 секунд
Лимит использования памяти 16 MiB
Входные данные #1
10 10
12
2 2
9 2
4 5
3 2
5 2
4 4
6 2
7 2
8 2
4 2
4 6
4 7
3 3 5
Выходные данные #1
2 3
Источник Региональная олимпиада по программированию, СибГИУ, 2011