OJ Board

Code: Select all

#include<iostream.h>

int main()
{
   int flag,s,i,j,t,n,seq[22],finseq[22],maxx,l,f,k;
   double mult,table[21][21];
   while(cin>>n)
   {
      for(i=0;i<n;i++)
      for(j=0;j<n;j++)
      if(i==j)
      table[i][j]=1.0;
      else
      cin>>table[i][j];
      
       finseq[0]=-1;   
      maxx=60;
      for(i=3;i<(1<<n);i++)
      {
         t=i; s=0; mult=1.0; l=-1; f=-1; k=0; flag=0;
         while(t!=0)
         {
            if(t%2==1)
            {
               if(l==-1)
               f=s;
               
               seq[s]=s;
               
               if(l!=-1)
               mult*=table[seq[l]][seq[s]];
               
               l=s;
               k++;
               if(k>=maxx)
               { flag=1; break; }
            }
            else
            seq[s]=-1;
            t/=2;
            s++;            
         }
         if(flag==1)
         continue;
         mult*=table[seq[l]][seq[f]];
         seq[s]=seq[f];
         
         s++;
         if(mult>1.01)
         if(k<maxx)
         {
            maxx=k; t=0;
            for(j=0;j<s;j++)
            if(seq[j]!=-1)
            { finseq[t]=seq[j]; t++; } 
            if(maxx==2)
            break;
         }
      }
      if(finseq[0]==-1)
      cout<<"no arbitrage sequence exists"<<endl;
      else
      for(j=0;j<=maxx;j++)   
      if(j==maxx)
      cout<<finseq[j]+1<<endl;
      else
      cout<<finseq[j]+1<<" ";   
   }
}

Code: Select all

#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<sstream>
using namespace std;
int main()
{ int n;
 outer: while((cin>>n)!=0)
  {
    
 /*   if(ret==EOF)
      break;*/
    vector<vector<double> > input(n,vector<double> (n));
    int i=0,j=0,k=0,l=0;
    for(i=0;i<n;i++)
    {
      for(j=0;j<n;j++)
      {
        if(i==j) { input[i][j]=1; continue;}
        scanf("%lf",&input[i][j]);
      }
    }
    vector< vector<double> > value(n,vector<double>(n));
    vector<vector<double> >  tmp(n,vector<double>(n));
    vector< vector<string> >  list(n,vector<string>(n));
    vector< vector<string> >  tmp_list(n,vector<string>(n));
    for(i=0;i<n;i++)
    {
      for(j=0;j<n;j++)
      {
        value[i][j]=input[i][j];
        char* str;
        int len=sprintf(str,"%d %d\n",i+1,j+1);
        //cout<<str<<"\n";
        list[i][j]=string(str,len);
        //cout<<list[i][j]<<"\n";
      }
    }
    //system("pause");
    

    bool flag=false;
    string ans("");
    double max=0;
    double out_max=0;
    for(i=1;i<n;i++)
    {
     
      
      for(j=0;j<n;j++)
      {
         flag=false;
         for(k=0;k<n;k++)
         {
           
           max=0;
           string newList;
           for(l=0;l<n;l++)
           {
              if(j==l) continue;
              if(input[j][l]*value[l][k]>max)
              {
                 max=input[j][l]*value[l][k];
                 newList=list[l][k];
              }
            }
            
            tmp[j][k]=max;
             stringstream out; out<<(j+1);
             string str_temp=out.str();
            str_temp+=" ";
            str_temp += newList;   
            
            tmp_list[j][k]=string(str_temp);
              if(tmp[j][k]>1.01 && j==k)
         {
           if(!flag) {ans=tmp_list[j][k]; out_max=tmp[j][k];flag=true;}
           else if(tmp_list[j][k].compare(ans)<0) {ans=tmp_list[j][k];out_max=tmp[j][k];}
         }
         }
         if(flag)
         {  cout<<ans;
            
            goto outer;
         }
       
       }
       vector<vector<double> >  tmp1(tmp);
    vector< vector<string> >  list2(tmp_list);
       value=tmp1; list=list2;
       
     }
     if(!flag)
       printf("no arbitrage sequence exists\n");
   }
 //system("pause");
 return 0; 
}
             
      

Code: Select all

#include <cstdlib>
#include <iostream>

using namespace std;

namespace {
  
  template<size_t N>
  inline void PrintSolution(const unsigned (&iPath)[N][N][N], unsigned iLength, unsigned iCurrency) {    
    for(unsigned aCurrency = iCurrency; iLength; --iLength) {
      cout << aCurrency << '-';
      aCurrency = iPath[iLength][iCurrency][aCurrency];
    }
    cout << iCurrency << endl;
  }

  template<size_t N>
  inline void MakeMoney(const double (& iConvertionTable)[N][N], size_t iNbCurrency) {

    static double aBest[N][N][N];
    static unsigned aPath[N][N][N];

    for(unsigned s = 2; s <= iNbCurrency; ++s)
      for(unsigned m = 1; m <= iNbCurrency; ++m)
	fill_n(aBest[s][m],iNbCurrency+1,0.);       

    for(unsigned m = 1; m <= iNbCurrency; ++m)     
      for(unsigned n = 1; n <= iNbCurrency; ++n) {
	aBest[1][m][n] = iConvertionTable[m][n];
	aPath[1][m][n] = n;
      }
	
    double d;
    for(unsigned s = 2; s <= iNbCurrency; ++s) {
      for(unsigned i = 1; i <= iNbCurrency; ++i)
	for(unsigned m = 1; m <= iNbCurrency; ++m) {
	  for(unsigned n = 1; n <= iNbCurrency; ++n) {
	    d = aBest[s-1][m][i] * aBest[1][i][n];
	    if(d > aBest[s][m][n]) {
	      aBest[s][m][n] = d;
	      aPath[s][m][n] = i;
	    }
	  } 
      }	

      for(unsigned m = 1; m <= iNbCurrency; ++m)
	if(aBest[s][m][m] > 1.01)
	  return PrintSolution(aPath,s,m);	

    }
   cout << "no arbitrage sequence exists" << endl;
  }
}

int main(int, char **) {
  unsigned aNbCurrency = 0;
  double aConvertionTable[21][21];
  while(!(cin >> aNbCurrency).eof()){
    for(unsigned i = 1; i <= aNbCurrency; ++i) {
      for(unsigned j = 1; j < i; ++j)
	cin >> aConvertionTable[j][i];
      aConvertionTable[i][i] = 1.;
      for(unsigned j = i+1; j <= aNbCurrency; ++j)
	cin >> aConvertionTable[j][i];
    }
    MakeMoney(aConvertionTable,aNbCurrency);
  }
  return EXIT_SUCCESS;
}

Code: Select all

4
1 0 0
1.005 0 0
0 0 0
0 0 0

Code: Select all

1 2 1 2 1