Задача Sightseeing
Август 2008 года. Каир. Международная олимпиада по информатике. Ознакомление участников олимпиады с городом было решено провести по следующей схеме: сначала участники K минут осматривают город сами, потом направляются к точке сбора на централизованную экскурсию. Район Каира, в котором находятся участники олимпиады, является прямоугольной сеткой улиц NхM. Координаты перекрестка задаются парой чисел (і, j). Северо-западный перекресток района имеет координаты (1,1) северо-восточный – (1,M), юго-западный– (N,1) и юго-восточный – (N,M). Обзор достопримечательностей происходит таким образом: очутившись на перекрестке, команда либо направляется на один из 4 соседних перекрестков, либо останавливается, в течение 5 минут любуется видами города, а затем повторяет выбор. Расстояние между перекрестками таково, что дорога от перекрестка к соседнему с ним перекрестку также занимает 5 минут. Для проведения централизованной экскурсии организаторы решили назначить точкой сбора перекресток, в котором, как ожидается, через K минут с начала экскурсии окажется максимальное количество команд. Зная город, организаторы для каждого перекрестка определили вероятность того, что команда из него пойдет на север, на запад, на юг, на восток или останется на месте. Исходя из этих данных, необходимо определить оптимальную точку сбора команд. В момент времени 0 все команди начинают обзор города с перекрестка (R,С). Известно, что команды не покидают пределы района.Технические условия: Программа Sightseeing читает с клавиатуры 5 чисел N, M, K, R и C (1<=N, M<=100, 0<=K<=500, K кратно 5, 1<=R<=N, 1<=C<=M) потом 5*N*M чисел – вероятность в описанной выше последовательности для перекрестков в порядке (1,1)...(1,M) (2,1)...(2,M)... (N,1)..(N,M). Вероятности - целые числа от 0 до 100, заданные в процентах. Сумма вероятностей для каждого перекрестка равняется 100. Программа выводит 3 числа, разделенные пробелами, - координаты искомой точки сбора и процент команд, которые, как ожидается, окажутся на этом перекрестке в момент K с точностью не менее 5 знаков после запятой или в экспоненциальной форме, не округляя.
Пример
Введение: 3 3 5 2 2 0 0 0 0 100 0 0 0 0 100 0 0 0 0 100 0 0 0 0 100 70 10 10 5 5 0 0 0 0 100 0 0 0 0 100 0 0 0 0 100 0 0 0 0 100
Выведение 1 2 70.0000000000