Задача Sightseeing
Серпень 2008 року. Каїр. Міжнародна олімпіада з інформатики. Ознайомлення учасників олімпіади з містом було вирішено провести за такою схемою: спочатку учасники K хвилин оглядають місто самі, потім прямують до точки збору на централізовану екскурсію. Район Каїра, в якому перебувають учасники олімпіади, є прямокутною сіткою вулиць NхM. Координати перехрестя задаються парою чисел (i, j). Північно-західне перехрестя району має координати (1,1), північно-східне – (1,M), південно-західне – (N,1) і південно-східне – (N,M). Огляд пам'яток проходить таким чином: опинившись на перехресті, команда або прямує на одне з 4 сусідніх перехресть, або зупиняється, протягом 5 хвилин милується краєвидами міста, а потім повторює вибір. Відстань між перехрестями така, що дорога від перехрестя до сусіднього з ним перехрестя також займає 5 хвилин. Для проведення централізованої екскурсії організатори вирішили призначити точкою збору перехрестя, в якому, як очікується, через K хвилин з початку екскурсії опиниться максимальна кількість команд. Знаючи місто, організатори для кожного перехрестя визначили ймовірність, що команда з нього піде на північ, на захід, на південь, на схід або залишиться на місці. Виходячи з цих даних, необхідно визначити оптимальну точку збору команд. У момент часу 0 всі команди починають огляд міста з перехрестя (R,C). Відомо, що команди не залишають меж району.
Технічні умови: Програма 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