Занятие 8

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