21/11/2024 20:20:38

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

657. Mortal Combat

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Краткое содержание фильма: для решающей битвы с силами зла были выбраны пять самых лучших бойцов Земли. Со стороны сил зла также будут сражаться пять бойцов. Каждый из бойцов сражается только один раз и только с одним противником. Чтобы Земля не была порабощена, каждый из бойцов Земли должен победить своего противника, а матч должен закончиться со счетом 5:0 в пользу Земли. Для каждой из возможных пар соперников известна вероятность `p_{ij}` победы `i`-го бойца Земли над `j`-ым бойцом сил зла. Требуется подобрать пары бойцов таким образом, чтобы вероятность счета 5:0 (т.е. `Πp_{ij}`) была максимальной.

Во входном файле пять строк по пять чисел (с точностью 3 разряда после запятой) в каждой строке – вероятности победы `p_{ij}\ (0\ <\ p_{ij}\ ≤\ 1)` для каждой пары бойцов, сначала строка с вероятностями для первого бойца Земли, затем для второго и т.д.

В выходной файл вывести пять целых чисел: номера противников `j_k` для каждого `k`-го бойца Земли, сначала номер противника для первого бойца, затем для второго и т.д. Если существует несколько вариантов, максимизирующих вероятность общей победы, вывести один (любой) из них.

Пример ввода

0.500 0.544 0.595 0.600 0.550
0.800 0.001 0.050 1.000 0.500
0.700 0.020 0.021 0.456 0.906
0.323 0.345 0.930 0.456 0.455
0.300 1.000 1.000 0.900 0.800

Вывод для примера

1 4 5 3 2

22/04/2001	Региональная олимпиада Информатика-2001 (4)
31/10/2007	Занятие 8 (E)
09/12/2010	Сборы 31 (2D)