Page 12 of 15

### hints.

Posted: Thu Jun 16, 2005 4:19 pm

Posted: Thu Jun 16, 2005 6:04 pm

1. http://www.cs.toronto.edu/~heap/270F02/node42.html
2. http://www.comp.nus.edu.sg/~stevenha/pr ... raph6.html

### 104...I give up

Posted: Wed Jun 29, 2005 4:39 pm
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.

Posted: Mon Jul 04, 2005 8:59 pm
Never mind...got AC...

Posted: Wed Sep 07, 2005 4:57 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);
}

}

### 104 WA - Precision?

Posted: Wed Oct 05, 2005 11:57 pm
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

Posted: Sat Nov 05, 2005 1:37 am
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".

### [104] Help to understand

Posted: Wed Jan 04, 2006 7:18 pm
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?

Posted: Wed Jan 04, 2006 8:29 pm
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!

Posted: Wed Jan 04, 2006 8:51 pm
oh! thnk you. i'm so inattentive... :'(

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

Posted: Fri Jan 06, 2006 3:53 am
--------------------------------------------------------------------------------------------
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?

Posted: Fri Jan 06, 2006 6:21 pm
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...

### thanks!!

Posted: Sat Jan 07, 2006 12:50 am
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.

### 104 arbitrage

Posted: Sat Jan 14, 2006 9:21 pm
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();
}
}

}

}
}

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

Posted: Sat Feb 04, 2006 2:59 pm
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))