Code: Select all
#include<iostream.h>
int main()
{
int flag,s,i,j,t,n,seq[22],finseq[22],maxx,l,f,k;
double mult,table[21][21];
while(cin>>n)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i==j)
table[i][j]=1.0;
else
cin>>table[i][j];
finseq[0]=-1;
maxx=60;
for(i=3;i<(1<<n);i++)
{
t=i; s=0; mult=1.0; l=-1; f=-1; k=0; flag=0;
while(t!=0)
{
if(t%2==1)
{
if(l==-1)
f=s;
seq[s]=s;
if(l!=-1)
mult*=table[seq[l]][seq[s]];
l=s;
k++;
if(k>=maxx)
{ flag=1; break; }
}
else
seq[s]=-1;
t/=2;
s++;
}
if(flag==1)
continue;
mult*=table[seq[l]][seq[f]];
seq[s]=seq[f];
s++;
if(mult>1.01)
if(k<maxx)
{
maxx=k; t=0;
for(j=0;j<s;j++)
if(seq[j]!=-1)
{ finseq[t]=seq[j]; t++; }
if(maxx==2)
break;
}
}
if(finseq[0]==-1)
cout<<"no arbitrage sequence exists"<<endl;
else
for(j=0;j<=maxx;j++)
if(j==maxx)
cout<<finseq[j]+1<<endl;
else
cout<<finseq[j]+1<<" ";
}
}