OJ Board

The Online Judge board
https://onlinejudge.org/board/

104 - Arbitrage

https://onlinejudge.org/board/viewtopic.php?t=652

Page 12 of 15

hints.

Posted: Thu Jun 16, 2005 4:19 pm
by Gaolious
http://online-judge.uva.es/board/viewto ... t=15#35471

Posted: Thu Jun 16, 2005 6:04 pm
by 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

104...I give up

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

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

104 WA, please help

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


}

104 WA - Precision?

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

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

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

[104] Help to understand

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

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

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

104 - Arbitrage, is my reasoning incorrect?

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

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

thanks!!

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

104 arbitrage

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


}


}
}

Re: 104 - Arbitrage, is my reasoning incorrect?

Posted: Sat Feb 04, 2006 2:59 pm
by 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.
All times are UTC+02:00
Page 12 of 15

Powered by phpBB® Forum Software © phpBB Limited