104 - Arbitrage

[Gaolious]

http://online-judge.uva.es/board/viewto ... t=15#35471

[Mohammad Mahmudur Rahman]

If you want to know about basic floyd warshall, these liknks may help you.

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

[mido]

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]

Never mind...got AC...

[xiliu.tang]

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]

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
/* Additional Test Cases
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]

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]

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]

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]

oh! thnk you. i'm so inattentive... :'(

[bjorn]

--------------------------------------------------------------------------------------------
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 
           received in less than #steps" 
      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]

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]

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]

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]

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 readdata(void)
{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))
{readdata();
process();
}
return 0;
}

if you have any testcases to show me,it will be helpful too.I see none in the forum.