Арбитражата е проблем на размена на една валута со друга валута со надеж дека ќе ги искористите малите разлики во курсната листа помеѓу валутите и ќе остварите профит. На пример ако со 1 американски долар може да се купи 0,7 бриатнски фунти, една фунта купува 9,5 франанци, а еден франк купува 0,16 амеракнски долари тогаш со помош на арбитражата може да започнете со еден американски долар, а на крај да завршите со 1,064 американски долари. Напишете програма со која ќе се проверува дали постои таква секвенца во курсната листа која ќе ви овозможи профит. За арбитражата да биде успешна мора да започнете и завршите со иста валута, а од која валута ќе започнете не е важно.

Влез

Bлезот се состои од број n и квадратна матрица n x n. Параметарот n го претставува бројот на валути достапни за размена, каде што максималната големина на n изнесува 20, а минималната 2. Матрицата всушност претставува курсната листа помеѓу валутите на различни земји. Првиот ред на матрицата ја претставува кусната листа за размена меѓу првата земја и останатите n-1 земји на курсната листа.

Излез

За внесената матрица програмата мора да пронајде секвенца на размена помеѓу валутите која обезбедува профит поголем од 1 процент(0.001), секако доколку таква постои.Ако постои таква секвенца, истата треба да се испечати.Ако има повеќе вакви секвенци кои резултираат со профит повеќе од 1 процент треба да се врати онаа со најмала должина, т.е. онаа што користи најмалку размени меѓу валути за да оствари профит.
Бидејќи УЈП ги следи должините на трасакциските секвенци, сите профитабилни секвенци мора да бидат составени од n (истото n од влезот) или помалку од n размени меѓу валути.На пример секвенцата 1-2-1 се состои од 2 размени. Секвенцата се печати во формат пр. 1-2-1, каде што бројките го претставуваат редоследот на линијата во матрицата(курсната листа) каде се наоѓа валутата што сме ја искористиле.Првата и последната бројка ја претставуваат валутата со која што сме почнале и завршиле(мора да биде иста).Ако не постои профитабилна секвенца пократка од n размени тогаш треба да се врати “ne postoi profitabilna sekvenca”.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
2
1.000 2.000
0.450 1.000

излез
ne postoi profitabilna sekvenca

влез
4
1.000 3.100   0.023 0.350
0.210 1.000   0.353 8.130
0.200 9.559   1.000 10.339
2.110 0.089   0.061 1.000

излез
2-3-2