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

1417. Космическая распальцовка

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
«Первое космическое негуманоидное казино» знаменито тем, что первым стало обслуживать как людей, так и негуманоидов. Очень быстро выяснилось, что большинство негуманоидов считает традиционные человеческие игры — космическую рулетку, космический блекджек, и т.п. — на редкость глупыми и скучными. Относительно популярен был покер с землянами, где по отражению карт в глазах можно было узнать карты соперника, но и он не был очень распространен. Как ни странно, самой большой популярностью среди негуманоидов пользовалась немудреная игра в пальцы, подсмотренная ими у каких-то подвыпивших космонавтов. Игра простая до неприличия: двое игроков считают вслух: Раз! — Два! — Три!, и одновременно показывают один или более разжатых пальцев. Переносная игровая приставка тут же подсчитывает показанные пальцы, и, глядя в заранее введенную в нее таблицу выигрышей-проигрышей, объявляет, кто из них проиграл и сколько денег он должен. Игра повторяется снова и снова, пока игроки не падают от выпивки или усталости. Негуманоиды требовали, чтобы в «Первом космическом негуманоидном казино» была такая же игра, и руководство пошло им навстречу.
Правила игры в «Космические пальцы» (а именно так окрестили эту игру в казино) очень просты: игрок дает крупье 20 космических рублей, после этого на счет «Три!» они вместе с крупье показывают руки с расжатыми пальцами. Конечно же, число пальцев (или щупалец) у негуманоидов может быть каким угодно, но казино гарантирует, что крупье будет иметь пальцев не меньше, чем игрок. Если количества разжатых пальцев у крупье и игрока совпали — игрок получает 1000 рублей. Если нет, то ничего не получает, или получает какую-нибудь утешительную сумму, не больше 10 рублей. Суммы утешительных выигрышей зависят от числа показанных игроком и крупье пальцев и указаны в специальной таблице выигрышей, которая напечатана на столе. Ваша задача — написать программу, подсказывающую крупье такие ходы, чтобы средняя прибыль казино была как можно больше. Надо предполагать, что дураков среди негуманоидов нет, поэтому игроки помнят таблицу выигрышей назубок и будут играть самым лучшим (для себя) образом.
Как написать такую программу? Ваш знакомый математик на этот вопрос недоуменно ответил, что это же классическая задача на минимакс, её решили ещё в прошлом веке, и вообще, как же можно не знать про матричные игры со смешанными стратегиями? Крупье просто должен выбирать число показываемых пальцев случайным образом, причем вероятность выбора этого числа должна быть такой, чтобы математическое ожидание выигрыша вообще не зависело от числа пальцев, показанных игроком. Что такое математическое ожидание? Это что-то вроде среднего выигрыша: сумма возможных выигрышей помноженных на вероятность их получения.

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

В первой строке число пальцев у игрока N (1 < N ≤ 100). Можно считать, что у крупье пальцев столько же. Далее — таблица выигрышей. В каждой строке таблицы указаны выигрыши игрока, показавшего соответствующее номеру строки (от 1 до N) число пальцев, номер столбца соответствует числу пальцев (от 1 до N), показанных крупье. Понятно, что на диагонали таблицы всегда стоят 1000, а в остальных клетках целые числа от 0 до 10.

Результат

Вывести, с точностью до пяти знаков после десятичной точки, вероятности, с которыми крупье должен показывать соответствующее число пальцев.

Пример

исходные данныерезультат
3
1000 10 10
0 1000 1
5 3 1000
0.32986
0.33623
0.33391
Автор задачи: Станислав Васильев
Источник задачи: Чемпионат Уральского государственного университета, 29 октября 2005