Анонс #208. Обмен валют

Задача: банк одной страны работает с 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 единицы.

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