I tested it many times but without any results(* Arbitrage *)
[pascal]Program p104 (input, output);
Const MaxN = 20;
Type PathMas = array[1..2*MaxN]of integer;
Var Exc : array[1..MaxN,1..MaxN]of extended;
Best : array[1..MaxN]of record Value : single; Pred,Len : Integer;K : PathMas; end;
Path : array[1..MaxN,0..MaxN]of Integer;
Use : array[1..MaxN]of integer;
N,i,j,k : Integer;
ok,p : Integer;
begin
while not eof(input) do begin
Read(Input,N);
for i:=1 to N do
for j:=1 to N do if i<>j then
Read(Input,Exc[i,j]);
for k:=1 to N do begin
ok:=0; Path[k,0]:=-1;
for i:=1 to N do Best.Value:=0;
Best[k].Value:=1000;
Best[k].K[1]:=k;
Best[k].Len:=1;
for p:=1 to N do
for i:=1 to N do begin
for j:=1 to N do if i<>j then
if Best.Value*Exc[i,j]>Best[j].Value then begin
Best[j].Value:=Best.Value*Exc[i,j];
Best[j].Pred:=i;
Best[j].K:=Best.K;
Best[j].Len:=Best.Len+1;
Best[j].K[Best[j].Len]:=j;
if j=k then
if Best[k].Value>1010.000000001 then begin
ok:=1;
break;
end;
end;
if ok=1 then break;
end;
if Best[k].Len>N then ok:=0;
if ok=1 then begin
for j:=1 to N do Path[k,j]:=Best[k].K[j];
Path[k,0]:=Best[k].Len;
end;
end;
j:=100;
for i:=1 to N do
if Path[i,0]<>-1 then
if Path[i,0]<j then j:=Path[i,0];
if j=100 then writeln(Output,'no arbitrage sequence exists') else begin
for i:=1 to N do
if Path[i,0]=j then begin
j:=i;
break;
end;
for i:=1 to Path[j,0]-1 do Write(Output,Path[j,i]:0,' ');
Writeln(Output,Path[j,Path[j,0]]:0);
end;
end;
end.[/pascal]
[Edited by fpnc to improve visibility via pascal BBCode]
