UniLecs #Task. Currency exchange

Задача: банк одной страны работает с N различными валютами. В банке утверждены курсы обмена любой валюты на любую другую. А именно, значение P[i][j] равно сумме, которую банк выплачивает в валюте j в обмен на единицу валюты i. При этом P[i][i]=1.

Вы бы хотели разорить банк, заработав неограниченно большую сумму денег используя только те курсы обмена валют, которые установлены самим банком. Выясните, удастся ли вам это сделать.

Входные данные

Программа получает на вход число N (1⩽N⩽50). Далее идет N строк по N действительных неотрицательных чисел в каждой строке — курсы обмена валют. j-е число i-й строке равно числу единиц валюты j, которое выдает банк в обмен на единицу валюты i.

Вывод: выведите true, если можно разорить банк и false в противном случае.

Примеры:

1. N = 2

[1, 2]

[0.5, 1]

Output: false

2. N = 3

[1, 2, 3]

[0.5, 1, 2]

[0.3, 0.5, 1]

Output: true

Пояснение ко 2му примеру: можно обменять единицу 1й валюты на 2 единицы 2й валюты. Далее можно обменять получившиеся 2 единицы 2й валюты на 4 единицы 3й валюты.

Наконец, 4 единицы 3й валюты можно обменять снова на 1ю валюту, но получив уже 1.2 единицы.

Соот-но, можно продолжить процесс и получить сколь угодно большую сумму.

Разбор

Можно обозначить валюты, как вершины графа, а курсы обмена на другую валюту — ребрами. Тогда задача сводится в общем случае к нахождению отрицательного цикла в графе. Для этого удобно использовать алгоритм Флойда.

Необходимо получить как можно большую сумму, поэтому модифицируем алгоритм Флойда, считая, что A[i][j] равно максимальной сумме, которую можно получить в валюте j из единицы валюты i при помощи обменных операций банка.

Значение A[i][j] обновляется по правилу:

A[i][j] = max(A[i][j], A[i][k] * A[k][j])

Можно получить неограниченно большую сумму, если после окончания алгоритма Флойда A[i][i] >1 для какого-то значения i, то есть можно совершить «циклический» обмен, увеличивающий исходную сумму в одной из валют.

Реализация

C#

https://gist.github.com/unilecs/50011a3494a10c329946674c0999368e

Play-test
https://dotnetfiddle.net/8VI8Hb