Загрузка [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
 

printЗанятие 8

printE. Mortal Combat

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

Краткое содержание фильма: для решающей битвы с силами зла были выбраны пять самых лучших бойцов Земли. Со стороны сил зла также будут сражаться пять бойцов. Каждый из бойцов сражается только один раз и только с одним противником. Чтобы Земля не была порабощена, каждый из бойцов Земли должен победить своего противника, а матч должен закончиться со счетом 5:0 в пользу Земли. Для каждой из возможных пар соперников известна вероятность pij победы i-го бойца Земли над j-ым бойцом сил зла. Требуется подобрать пары бойцов таким образом, чтобы вероятность счета 5:0 (т.е. Π) была максимальной.
Во входном файле пять строк по пять чисел (с точностью 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

loading