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