104 - Arbitrage
Moderator: Board moderators
-
- New poster
- Posts: 11
- Joined: Sat Nov 17, 2001 2:00 am
Agian, works with the sample input but when we send it the reply is a wron answer. We use a backtracking algorithm to check all the possible outcomes. First we check if there is a profit in two steps. If there is we find the max profit in two steps and output it. If there is not then we check if there si profit in 3 steps and so on.
//@begin_of_source_code
/*@JUDGE_ID: 15975FF 104 C++*/
#include<iostream.h>
double C[22][22];
int n;
int Steps[22];
int length;
double rate;
double profit;
int Temp[22];
bool flag;
bool CheckTemp(int i, int k)
{
int j;
for( j = 1; j<k; j++)
{
if( Temp[j] ==i)
return false;
}
return true;
}
bool Convert(int k, int j)
{
int i;
rate = 1;
for(i = 2; i <k; i++)
{
rate = rate*C[Temp[i-1]][Temp];
}
rate = rate * C[Temp[k-1]][j];
rate = rate * C[j][1];
if(rate > 1.01)
return true;
return false;
}
void Solve(int k)
{
int i,j;
for(i = 2; i <=n; i++)
{
if(CheckTemp(i,k) && Convert(k,i))
{
if( !flag)
{
Temp[k] = i;
flag = true;
length = k;
profit = rate;
for( j = 1; j <= k; j++)
{
Steps[j] = Temp[j];
}
}
else if(k == length && rate > profit)
{
Temp[k] = i;
profit = rate;
for( j = 1; j <= k; j++)
{
Steps[j] = Temp[j];
}
}
//else if(k < length)
//{
// Temp[k] = i;
// Solve(k+1);
//}
}
}
if(!flag && k < n)
{
for(i = 2; i <=n; i++)
{
if( CheckTemp(i,k))
{
Temp[k] = i;
Solve(k+1);
}
}
}
}
int main()
{
int i,j;
while(cin>>n)
{
for( i = 1; i <=n; i++)
{
for(j = 1; j <=n; j++)
{
if(i == j)
C[j] = 1.0;
else
cin>>C[j];
}
}
flag =false;
profit = 0;
Temp[1] = 1;
Solve(2);
if(flag)
{
for( i = 1; i <=length; i++)
cout<<Steps<< ' ';
cout << 1 <<endl;
}
else
cout<<"no arbitrage sequence exists" << endl;
}
return 0;
}
//@end_of_source_code
//@begin_of_source_code
/*@JUDGE_ID: 15975FF 104 C++*/
#include<iostream.h>
double C[22][22];
int n;
int Steps[22];
int length;
double rate;
double profit;
int Temp[22];
bool flag;
bool CheckTemp(int i, int k)
{
int j;
for( j = 1; j<k; j++)
{
if( Temp[j] ==i)
return false;
}
return true;
}
bool Convert(int k, int j)
{
int i;
rate = 1;
for(i = 2; i <k; i++)
{
rate = rate*C[Temp[i-1]][Temp];
}
rate = rate * C[Temp[k-1]][j];
rate = rate * C[j][1];
if(rate > 1.01)
return true;
return false;
}
void Solve(int k)
{
int i,j;
for(i = 2; i <=n; i++)
{
if(CheckTemp(i,k) && Convert(k,i))
{
if( !flag)
{
Temp[k] = i;
flag = true;
length = k;
profit = rate;
for( j = 1; j <= k; j++)
{
Steps[j] = Temp[j];
}
}
else if(k == length && rate > profit)
{
Temp[k] = i;
profit = rate;
for( j = 1; j <= k; j++)
{
Steps[j] = Temp[j];
}
}
//else if(k < length)
//{
// Temp[k] = i;
// Solve(k+1);
//}
}
}
if(!flag && k < n)
{
for(i = 2; i <=n; i++)
{
if( CheckTemp(i,k))
{
Temp[k] = i;
Solve(k+1);
}
}
}
}
int main()
{
int i,j;
while(cin>>n)
{
for( i = 1; i <=n; i++)
{
for(j = 1; j <=n; j++)
{
if(i == j)
C[j] = 1.0;
else
cin>>C[j];
}
}
flag =false;
profit = 0;
Temp[1] = 1;
Solve(2);
if(flag)
{
for( i = 1; i <=length; i++)
cout<<Steps<< ' ';
cout << 1 <<endl;
}
else
cout<<"no arbitrage sequence exists" << endl;
}
return 0;
}
//@end_of_source_code
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
Try this test:
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
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
The (one of) correct output is:
5 6 5
10 16 10 16 10
You need to change your algorithm anyway -- your code hangs at second test case...
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
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
The (one of) correct output is:
5 6 5
10 16 10 16 10
You need to change your algorithm anyway -- your code hangs at second test case...
Why WA ? 
/* @JUDGE_ID: xxxxx 104 C++ DP */
#include <iostream.h>
#include <math.h>
double a[20][20],d[20][20],tmp,val = log(1.01);
int n,i,j,k,l,tr[20][20],min,path[20];
void main()
{
while (cin >> n)
{
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i == j) a = 0.0;
else
{
cin >> tmp;
if (tmp == 0.0) a[j] = -1e20;
else a[j] = log(tmp);
}
min = n;
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
d[0] = a[k];
tr[0] = k;
}
for (i = 1; i < n; i++)
{
if (i >= min) break;
for (j = 0; j < n; j++) d[j] = -1e20;
for (j = 0; j < n; j++)
for (l = 0; l < n; l++)
if (d[j] < d[i-1][l] + a[l][j])
{
d[j] = d[i-1][l] + a[l][j];
tr[i][j] = l;
}
if (d[i][k] >= val)
{
min = i; j = k; l = i;
while (l >= 0)
{
path[l + 1] = j;
j = tr[l][j];
l--;
}
path[0] = k;
break;
}
}
}
if (min == n + 1) cout << "no arbitrage sequence exists" << endl;
else
{
for (i = 0; i <= min; i++) cout << path[i] + 1 << ' ';
cout << path[min + 1] + 1 << endl;
}
}
}

/* @JUDGE_ID: xxxxx 104 C++ DP */
#include <iostream.h>
#include <math.h>
double a[20][20],d[20][20],tmp,val = log(1.01);
int n,i,j,k,l,tr[20][20],min,path[20];
void main()
{
while (cin >> n)
{
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i == j) a = 0.0;
else
{
cin >> tmp;
if (tmp == 0.0) a[j] = -1e20;
else a[j] = log(tmp);
}
min = n;
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
d[0] = a[k];
tr[0] = k;
}
for (i = 1; i < n; i++)
{
if (i >= min) break;
for (j = 0; j < n; j++) d[j] = -1e20;
for (j = 0; j < n; j++)
for (l = 0; l < n; l++)
if (d[j] < d[i-1][l] + a[l][j])
{
d[j] = d[i-1][l] + a[l][j];
tr[i][j] = l;
}
if (d[i][k] >= val)
{
min = i; j = k; l = i;
while (l >= 0)
{
path[l + 1] = j;
j = tr[l][j];
l--;
}
path[0] = k;
break;
}
}
}
if (min == n + 1) cout << "no arbitrage sequence exists" << endl;
else
{
for (i = 0; i <= min; i++) cout << path[i] + 1 << ' ';
cout << path[min + 1] + 1 << endl;
}
}
}
Sorry, I posted a wrong source code in previous message. Here's my WA program :
/* @JUDGE_ID: xxxxx 104 C++ DP */
#include <iostream.h>
#include <math.h>
double a[20][20],d[20][20],tmp,val = log(1.01);
int n,i,j,k,l,tr[20][20],min,path[20];
void main()
{
while (cin >> n)
{
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i == j) a = 0.0;
else
{
cin >> tmp;
if (tmp == 0.0) a[j] = -1e20;
else a[j] = log(tmp);
}
min = n + 1;
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
d[0] = a[k];
tr[0] = k;
}
for (i = 1; i < n; i++)
{
if (i >= min) break;
for (j = 0; j < n; j++) d[j] = -1e20;
for (j = 0; j < n; j++)
for (l = 0; l < n; l++)
if (d[j] < d[i-1][l] + a[l][j])
{
d[j] = d[i-1][l] + a[l][j];
tr[i][j] = l;
}
if (d[i][k] > val)
{
min = i; j = k; l = i;
while (l >= 0)
{
path[l + 1] = j;
j = tr[l][j];
l--;
}
path[0] = k;
break;
}
}
}
if (min == n + 1) cout << "no arbitrage sequence exists" << endl;
else
{
for (i = 0; i <= min; i++) cout << path[i] + 1 << ' ';
cout << path[min + 1] + 1 << endl;
}
}
}
/* @JUDGE_ID: xxxxx 104 C++ DP */
#include <iostream.h>
#include <math.h>
double a[20][20],d[20][20],tmp,val = log(1.01);
int n,i,j,k,l,tr[20][20],min,path[20];
void main()
{
while (cin >> n)
{
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i == j) a = 0.0;
else
{
cin >> tmp;
if (tmp == 0.0) a[j] = -1e20;
else a[j] = log(tmp);
}
min = n + 1;
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
d[0] = a[k];
tr[0] = k;
}
for (i = 1; i < n; i++)
{
if (i >= min) break;
for (j = 0; j < n; j++) d[j] = -1e20;
for (j = 0; j < n; j++)
for (l = 0; l < n; l++)
if (d[j] < d[i-1][l] + a[l][j])
{
d[j] = d[i-1][l] + a[l][j];
tr[i][j] = l;
}
if (d[i][k] > val)
{
min = i; j = k; l = i;
while (l >= 0)
{
path[l + 1] = j;
j = tr[l][j];
l--;
}
path[0] = k;
break;
}
}
}
if (min == n + 1) cout << "no arbitrage sequence exists" << endl;
else
{
for (i = 0; i <= min; i++) cout << path[i] + 1 << ' ';
cout << path[min + 1] + 1 << endl;
}
}
}
I get right with the test data,but i still get WA
here is my code:
#include <stdio.h>
void main()
{
double now[20];
double next[20];
double exchange[20][20];
int len[20][100];
int i,j,k;
int dim;
int flag=0;
int times=0;
int flag1=0;
while(scanf("%d",&dim)!=EOF)
{
for(i=0;i<20;i++)
{
now=0;
next=0;
for(j=0;j<20;j++)
exchange[j]=0;
for(j=0;j<100;j++)
len[j]=0;
}
for(i=0;i<dim;i++)
{
for(j=0;j<dim;j++)
{
if(i==j)
continue;
scanf("%lf",&exchange[j]);
}
}
now[0]=1;
next[0]=1;
for(i=1;i<dim;i++)
{
now=exchange[0];
next=exchange[0];
}
for(i=0;i<dim;i++)
len[0]=i+1;
times=0;
flag1=0;
while(1)
{
times++;
flag=0;
for(i=0;i<dim;i++)
{
for(j=0;j<dim;j++)
{
if(now[i]*exchange[i][j]>now[j])
{
if(j==0)
flag1=1;
next[j]=now[i]*exchange[i][j];
for(k=0;k<times;k++)
len[j][k]=len[i][k];
len[j][times]=j+1;
flag=1;
}
}
}
for(j=0;j<dim;j++)
now[j]=next[j];
if(flag1==1)
break;
if(flag==0)
break;
}
if(flag==0)
printf("no arbitrage sequence existsn");
else if(flag1==1)
{
printf("1");
for(i=0;i<=times;i++)
printf(" %d",len[0][i]);
printf("n");
}
}
}
here is my code:
#include <stdio.h>
void main()
{
double now[20];
double next[20];
double exchange[20][20];
int len[20][100];
int i,j,k;
int dim;
int flag=0;
int times=0;
int flag1=0;
while(scanf("%d",&dim)!=EOF)
{
for(i=0;i<20;i++)
{
now=0;
next=0;
for(j=0;j<20;j++)
exchange[j]=0;
for(j=0;j<100;j++)
len[j]=0;
}
for(i=0;i<dim;i++)
{
for(j=0;j<dim;j++)
{
if(i==j)
continue;
scanf("%lf",&exchange[j]);
}
}
now[0]=1;
next[0]=1;
for(i=1;i<dim;i++)
{
now=exchange[0];
next=exchange[0];
}
for(i=0;i<dim;i++)
len[0]=i+1;
times=0;
flag1=0;
while(1)
{
times++;
flag=0;
for(i=0;i<dim;i++)
{
for(j=0;j<dim;j++)
{
if(now[i]*exchange[i][j]>now[j])
{
if(j==0)
flag1=1;
next[j]=now[i]*exchange[i][j];
for(k=0;k<times;k++)
len[j][k]=len[i][k];
len[j][times]=j+1;
flag=1;
}
}
}
for(j=0;j<dim;j++)
now[j]=next[j];
if(flag1==1)
break;
if(flag==0)
break;
}
if(flag==0)
printf("no arbitrage sequence existsn");
else if(flag1==1)
{
printf("1");
for(i=0;i<=times;i++)
printf(" %d",len[0][i]);
printf("n");
}
}
}