## 104 - Arbitrage

Moderator: Board moderators

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

### hints.

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

1. http://www.cs.toronto.edu/~heap/270F02/node42.html
2. http://www.comp.nus.edu.sg/~stevenha/pr ... raph6.html
You should never take more than you give in the circle of life.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

### 104...I give up

What's wrong with this code?:

Code: Select all

``````#include <iostream>

using namespace std;

#define EPS 1e-8

void output(int s,int t,int w,int p[30][30][30])
{
if (w==0) cout<<s+1;
else output(s,p[s][t][w],w-1,p),cout<<" ",cout<<t+1;
}

void main()
{
double arr[30][30][30];
int n,p[30][30][30];

while (cin>>ws>>n)
{
int i,j,k,w;

for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
for (k=0;k<n;k++) arr[i][j][k] = 0.0,p[i][j][k]=0;
p[i][j][1] = i;
if (i!=j) cin>>arr[i][j][1];
}
arr[i][i][1] = 1.0;
}

for (w=2;w <= n;w++)
{
for (k=0;k < n;k++)
{
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
double tmp = arr[i][k][w-1]*arr[k][j][1];
if (tmp > arr[i][j][w] + EPS) arr[i][j][w]=tmp, p[i][j][w]=k;
}
}
}
}

int min_len = 50,index=-1;
for (w = n;w >= 2;w--)
{
double best = 1.0;
for (i=0;i<n;i++)
{
if (arr[i][i][w]>1.01+EPS && arr[i][i][w]>best+EPS)
{
index=i,min_len=w,best = arr[i][i][w];
}
}
}

if (index==-1) cout<<"no arbitrage sequence exists"<<endl;
else output(index,index,min_len,p),cout<<endl;

}

}
``````
Thanks for the time.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
Never mind...got AC...

xiliu.tang
New poster
Posts: 1
Joined: Wed Sep 07, 2005 4:52 pm

I run pass with all the test cases I can find in the forum, but get WA after submiting, please help, thanks.
#include <iostream>
#include <list>
using namespace std;
#ifndef ONLINE_JUDGE
#include <fstream>
ifstream _xin("a.txt");
#define cin _xin
#endif
#define MAX_DEC 30

void print_path(list<int> &l)
{
list<int>::iterator mi;
list<int>::iterator i;
int mini = MAX_DEC;
int j = 0;
for (i=l.begin(); i != l.end(); i++, j++)
if (*i<mini) {
mi = i;
mini = *i;
}
cout << *mi + 1;
for (j-=2, mi++; j>0; j--, mi++) {
if (mi == l.end()) {
mi = l.begin();
}
cout << ' ' << *mi + 1;
}
cout << ' ' << mini + 1;
cout << endl;
return;
}

void join(list<int> &dest, list<int> &l1, list<int> &l2)
{
list<int> xl;
list<int>::iterator i;
for(i=l1.begin(); i!=l1.end(); i++)
xl.push_back(*i);
i = l2.begin();
for(i++; i!=l2.end(); i++)
xl.push_back(*i);
dest.clear();
for (i=xl.begin(); i!=xl.end(); i++)
dest.push_back(*i);
return;
}
void profit(double a[MAX_DEC][MAX_DEC],
list<int> path[MAX_DEC][MAX_DEC],
int n)
{
int i, j, k;
for (k=0; k<n; k++) {
double prof = 1.0;
for (i=0; i < n; i++)
for(j=0; j < n; j++) {
if (a[k]*a[k][j] > a[j]) {
double tmp = a[j];
a[j] = a[k]*a[k][j];
#ifdef _DEBUG
printf("path[%d][%d]\n", i+1, k+1);
print_path(path[k]);
printf("path[%d][%d]\n", k+1, j+1);
print_path(path[k][j]);
#endif
join(path[j], path[k], path[k][j]);
#ifdef _DEBUG
printf ("a[%d][%d](%f) = a[%d][%d](%f)*a[%d][%d](%f):(%f), path[%d][%d] = %d\n",
i+1, j+1, tmp, i+1, k+1, a[k], k+1, j+1, a[k][j], a[j], i+1, j+1, k+1);
printf("path[%d][%d]\n", i+1, j+1);
print_path(path[i][j]);
#endif
}
if (i == j && a[i][j] > 1.01) {
print_path(path[i][j]);
#ifdef _DEBUG
cout << "profit is:"<< a[i][j] << endl;
cout << "k is:" << k << endl;
#endif
return;
}
}
}
cout << "no arbitrage sequence exists" << endl;
return;
}

int main(int argc, char **argv)
{
int n;
while (cin>>n) {
double a[MAX_DEC][MAX_DEC] = { {0} };
list<int> path[MAX_DEC][MAX_DEC];
int i, j;

for(i=0; i < n; i++)
for(j=0; j < n; j++)
if (i == j) {
a[i][j] = 1.0;
} else {
cin >> a[i][j];
path[i][j].push_back(i);
path[i][j].push_back(j);
}

profit(a, path, n);
}

}

BJM
New poster
Posts: 7
Joined: Sat Nov 16, 2002 3:28 pm

### 104 WA - Precision?

I've tried the test cases on the board and all come up OK, but I still get a WA. Any thoughts? If it's another precision thing then I'm giving up!

Can someone who got AC blast the following cases through and let me know if they get the same output. I know that the last few are correct if you use EXACT arithmetic - i.e. no rounding AT ALL - for example the last one gives a result which is:

1.01000000000006434388668492285546792130944671547196447929482389637107356374191802709539861369205977896583603678185280560336534840538792961024

this, is >1.01, when the transactions are done EXACTLY although it has got 140 digits after the decimal point.

Thanks a million

//Problem 104
20
0.38 0.88 0.33 0.85 0.76 0.62 0.15 0.69 0.42 0.96 0.19 0.62 0.54 0.90 0.95 0.08 0.99 0.78 0.42
0.51 0.86 0.43 0.20 0.21 0.27 0.24 0.21 0.20 0.37 0.11 0.74 0.50 0.44 0.52 0.71 0.62 0.49 1.03
0.51 0.06 0.83 0.68 0.60 0.48 0.37 0.11 0.15 0.68 0.47 0.54 0.63 0.80 0.49 0.23 0.87 1.03 0.57
0.37 0.62 0.55 0.94 0.58 0.61 0.09 0.85 0.69 0.78 0.92 0.89 0.76 0.46 0.25 0.83 0.21 0.49 0.12
0.01 0.40 0.31 0.09 0.38 0.42 1.03 0.81 1.00 0.04 0.91 0.46 0.21 0.41 0.05 0.65 0.69 0.84 0.70
0.88 1.04 0.69 0.38 0.61 0.57 0.36 0.24 0.72 0.12 0.95 0.71 0.98 0.56 0.34 0.76 0.33 0.68 0.94
0.03 0.40 0.73 0.70 0.25 0.24 0.41 0.92 0.71 0.87 0.23 0.75 0.76 0.59 0.51 1.00 0.55 0.62 0.70
0.65 0.72 0.95 0.65 0.40 0.99 0.59 0.25 0.85 0.80 0.45 0.64 0.46 0.36 0.77 0.28 0.92 0.24 0.92
0.78 0.49 0.05 0.01 0.73 0.06 0.98 0.67 0.29 0.27 0.48 0.43 0.46 0.61 0.71 0.76 0.56 0.28 0.33
0.81 0.73 0.92 0.16 0.97 0.77 1.03 0.86 0.38 0.62 0.89 0.48 0.45 0.08 1.04 0.76 0.11 0.20 0.18
0.63 0.70 0.49 0.64 0.73 0.51 0.41 0.51 0.35 0.31 0.33 0.75 0.10 0.84 0.94 0.90 1.02 0.33 0.80
0.67 0.57 0.94 0.86 0.02 0.67 0.14 0.49 0.75 0.82 0.41 0.28 0.45 0.31 0.31 0.32 0.21 0.03 0.78
0.26 0.88 0.17 0.01 0.56 0.04 0.93 1.04 0.79 0.39 0.36 0.69 0.65 0.80 0.99 0.30 0.42 1.00 0.99
0.42 0.10 0.00 0.35 0.38 0.56 0.64 1.01 0.67 0.55 0.56 0.41 0.05 0.16 0.42 0.74 0.40 0.26 0.83
0.58 1.03 0.66 0.16 0.84 0.06 0.69 1.04 0.62 0.77 0.98 0.67 0.50 0.05 0.74 0.60 0.89 0.91 1.03
0.57 0.68 0.95 0.99 0.27 0.14 1.02 0.34 0.23 0.97 0.22 0.66 0.70 0.09 0.64 0.20 0.39 0.14 1.04
0.37 0.14 0.50 0.64 0.30 0.17 1.00 1.01 0.98 0.34 1.03 0.72 0.94 0.67 0.74 0.82 0.75 0.57 0.69
0.84 0.29 0.53 0.01 0.77 0.09 0.93 0.94 0.11 0.32 0.36 0.11 1.00 0.38 0.30 0.74 0.80 0.77 0.94
0.04 0.48 0.97 0.54 0.81 0.33 0.67 0.10 0.83 0.94 0.22 0.52 0.90 0.62 0.79 0.90 0.40 0.26 0.23
0.55 0.48 0.75 0.96 0.65 0.21 0.98 0.71 0.91 0.63 0.94 0.62 0.56 0.90 0.89 0.00 0.43 0.43 0.08
3
1.2 .89
.88 5.1
1.1 0.15
4
3.1 0.0023 0.35
0.21 0.00353 8.13
200 180.559 10.339
2.11 0.089 0.06111
2
2.0
0.45
6
0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.1 0.0 0.0
0.0 0.0 1.0 0.0 0.0
0.0 5.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 9.0
0.0 0.0 0.0 0.0 1.0
20
1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454
1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20
1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455
1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00099552829497
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00099552829498
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Output
10 16 10 16 10
1 2 1
1 2 4 1
no arbitrage sequence exists
5 6 5
no arbitrage sequence exists
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1
no arbitrage sequence exists
1 20 1 20 1 20 1 20 1 20 1 20 1 20 1 20 1 20 1 20 1

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
Your algorithm, as written, is wrong: it doesn't return the shortest arbitrage sequence but the one with minimum starting point (albeit breaking ties by sequence length).
The outermost loop should be the one indexed by the variable "j".

StepLg
New poster
Posts: 6
Joined: Wed Dec 28, 2005 10:09 am
Contact:

### [104] Help to understand

The example #1:

Giving anwer is 1-2-1, the profit is 1.2*0.88=1.056-1.0\$

But why the sequence 1-2-3-1 is wrong? The profit in this case is 1.2*5.1*1.1=6.732-1.0\$

Where I am wrong?

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
This is the reason to your question:
If there is more than one sequence that results in a profit of more than 1 percent you must print a sequence of minimal length, i.e., one of the sequences that uses the fewest exchanges of currencies to yield a profit.
Good luck!

StepLg
New poster
Posts: 6
Joined: Wed Dec 28, 2005 10:09 am
Contact:
oh! thnk you. i'm so inattentive... :'(

bjorn
New poster
Posts: 2
Joined: Fri Jan 06, 2006 3:35 am

### 104 - Arbitrage, is my reasoning incorrect?

--------------------------------------------------------------------------------------------
MAIN PLEDGE FOR PEOPLE NOT WANTING TO READ WHOLE POST:
Please give me more sample input this problem is killing me.
--------------------------------------------------------------------------------------------

I have read all posts about people doing this problem with floyd-warshall,
using a 3D array, where the best exchange sequence from every currency to every other currency is stored for every number of steps.

I have however done it the following (not blazingly fast) way:

Code: Select all

``````for each starting currency
for #steps in 1..20
for each currency J do
for each currency K do
"for each currency K, calculate the largest amount we can possibly get of that
currency by trying an exchange from the best result for each currency J
end
end
"check if there was a sequence giving arbitrage by doing an exchange back
to starting currency. If so, and that sequence is also shorter than any found
before, store it, and continue with next 'starting currency'"
end
end
"output shortest sequence found"
``````
So I dont store a value for each step, but rather store the best possible amount of each currency in #steps or less in each iteration.

I have tried all sample inputs available on the forum and they give a correct result.
Should I be worrying about something else? I use (> 1.01) in my code. Or is there something fundamental that I am missing with my solution method here?

Dmitry R
New poster
Posts: 7
Joined: Sat Sep 17, 2005 10:42 am
Contact:
Do you count an exchange to starting currency as an exchange operation? If no, it can become a 21st exchange and your program will still output that there is a sequence of not more than 20 exchanges...

bjorn
New poster
Posts: 2
Joined: Fri Jan 06, 2006 3:35 am

### thanks!!

Thank you,

I got it right now in like 1 minute after your hint. So easy to look past some detail, in this case I had mistaken the limit to be 20 sequences, when it was actually n depending on the dimension of the input table. and counted one step too many as you hinted about.

msimonet
New poster
Posts: 1
Joined: Sat Jan 14, 2006 9:19 pm

### 104 arbitrage

I have a problem of WA with this C++ algorithm..
can you help me

#include <iostream>
#include <stack>
#include <stdio.h>

using namespace std;

int nbprec[25][25];
int prec[25][25];
float d[25][25];
float w[25][25];
bool avue[25][25][25];
int longueur;
int start;
stack<int> pile;
float maxi;

void relacher(int u,int v,int s,int n)
{

if(d[s]!=0 && nbprec[s]<n)
{
if(d[s][v]==0)
{
d[s][v]=d[s] * w[v];
prec[s][v]=u;
nbprec[s][v]=nbprec[s]+1;
}
else
{
if(d[s][v] < d[s] * w[v] && !avue[s][v])
{
d[s][v]=d[s] * w[v];
prec[s][v]=u;
nbprec[s][v]=nbprec[s][u]+1;
for(int k=1;k<=n;k++)
{
avue[s][k][v] = avue[s][k][u];
}
avue[s][v][v] = true;

}
}

}

}

void Bellman_Ford(int n,int s)
{
for(int i=1;i<=n;i++)
{
d[s] = 0;
prec[s] = 0;
nbprec[s] = 0;
}
d[s][s] = 1;

for(int k=1;k<n;k++)
{

for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
relacher(i,j,s,n);
}

if(d[s][s]>1.01)
{
i=n+1;
//j=n+1;
}

}
}

}

int main()
{
int n;
bool first = true;
while(!cin.eof())
{
cin >> n;
if(!cin.eof())
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
avue[j][k]=false;
}
avue[j][j]=true;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j)
{
cin >> w[j];
}
else
{
w = 1;
}

}
}

longueur = n+1;
maxi = 0;
start = 0;

for(int i=1;i<=n;i++)
{
Bellman_Ford(n,i);
if(d > 1.01)
{
if(nbprec[i][i] < longueur)
{
longueur = nbprec[i][i];
start = i;
maxi = d[i][i];
}
}
}

if(!first)
{
cout << endl;
}
first = false;
if(start == 0)
{
cout << "no arbitrage sequence exists";
}
else
{
int curr = start;
for(int i=1;i<=longueur;i++)
{
pile.push(curr);
curr = prec[start][curr];
}

cout << start;
while(!pile.empty())
{
cout << " " << pile.top();
pile.pop();
}
}

}

}
}

Apprentice
New poster
Posts: 1
Joined: Sat Feb 04, 2006 2:46 pm
Location: Mianyang Sichuan
Contact:

### Re: 104 - Arbitrage, is my reasoning incorrect?

I had one similar algorithm as yours at first,and I got WA.And then
I copied exactly your one.But still I got WA.
Can you help me find out what my problem is please.Here's my code:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int shortest,n,etimes;
double ctable[21][21];
double finestr[21][21][21];

int finestpr[21][21][21];

int shortests[23];

{int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
{for(j=1;j<i;j++)
scanf("%lf",&ctable[j]);
for(j=i+1;j<=n;j++)
scanf("%lf",&ctable[j]);
ctable=double(1);
scanf("\n");
}
/* printf("%d\n",n);
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
printf("%.2lf ",ctable[j]);
printf("\n");
}*/
return 0;
}

int done(void)
{int i,j,k;
for(i=1;i<=n;i++)
if(fabs(finestr[etimes]-1)>0.000000000001&&(finestr[etimes]>1))
{j=i;
for(k=etimes;k>=1;k--)
{shortests[k+1]=j;
j=finestpr[k][j];
}
shortests[1]=j;
for(k=1;k<=etimes+1;k++)
printf("%d ",shortests[k]);
printf("\n");
return 1;
}
return 0;
}

int process(void)
{int s,i,j,k,pr;
double t;
etimes=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{finestr[etimes][i][j]=ctable[i][j];
finestpr[etimes][i][j]=i;
}
while(etimes<n)
{etimes++;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{//////////////////
pr=1;
finestr[etimes][i][j]=finestr[etimes-1][i][pr]*ctable[pr][j];
finestpr[etimes][i][j]=pr;
for(pr=2;pr<=n;pr++)
{t=finestr[etimes-1][i][pr]*ctable[pr][j];
if(t>finestr[etimes][i][j])
{finestr[etimes][i][j]=t;
finestpr[etimes][i][j]=pr;
}
}

////////////////
}
if(done())
return 0;
}
printf("no arbitrage sequence exists\n");
return 0;
}

int main(void)
{while(!feof(stdin))