Cod sursa(job #174340)

Utilizator alecmanAchim Ioan Alexandru alecman Data 8 aprilie 2008 19:52:53
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<stdio.h>

#define INPUT "loto.in"
#define OUTPUT "loto.out"
#define NMAX 1000001

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

int N;

long S, a[ NMAX ], sum[ NMAX ][ 5 ];

void readValues()
{
  fscanf(fin, "%d %ld", &N, &S);

  for(int i = 1; i <= N; ++i)
    fscanf(fin, "%ld", &a[ i ]);
}

void setInitial()
{
  long cont = 1;

  for(int i = 1; i <= N; ++i)
    for(int j = 1; j <= N; ++j)
      for(int k = 1; k <= N; ++k)
      {
        sum[ cont ][ 0 ] = a[ i ] + a[ j ] + a[ k ];
	sum[ cont ][ 1 ] = a[ i ];
	sum[ cont ][ 2 ] = a[ j ];
	sum[ cont++ ][ 3 ] = a[ k ];
      }
}

inline void exchange(long& val1, long& val2)
{
  val1 = val1 + val2;
  val2 = val1 - val2;
  val1 = val1 - val2;
}

void quickSort(long st, long dr)
{
  long l = st, m = dr;

  while( l != m)
  {
    if( ( l < m && sum[ l ][ 0 ] > sum[ m ][ 0 ]) || ( l > m && sum[ l ][ 0 ] < sum[ m ][ 0 ] ) )
    {
      exchange( sum[ l ][ 0 ], sum[ m ][ 0 ]);
      exchange( sum[ l ][ 1 ], sum[ m ][ 1 ]);
      exchange( sum[ l ][ 2 ], sum[ m ][ 2 ]);
      exchange( sum[ l ][ 3 ], sum[ m ][ 3 ]);
      exchange( l, m);

      if(l < m)
	--m;
      else
	++m;
    }
    else
    if(l < m)
      --m;
    else
      ++m;
  }

  if(l != st) quickSort( st, l - 1);
  if(l != dr) quickSort( l + 1, dr);
}

void printSolution(int code, long fValue, long sValue)
{
  if(code == 1)
  {
    fprintf(fout, "%ld %ld %ld ", sum[ fValue ][ 1 ], sum[ fValue ][ 2 ], sum[ fValue ][ 3 ]);
    fprintf(fout, "%ld %ld %ld\n", sum[ sValue ][ 1 ], sum[ sValue ][ 2 ], sum[ sValue ][ 3 ]);
  }
  else
    fprintf(fout, "-1\n");
}

void binSearch()
{
  int Valid = 1;
  long st = 1, dr = N * N * N;

  while( st < dr && Valid)
  {
    if(sum[ st ][ 0 ] + sum[ dr ][ 0 ] == S)
    {
      printSolution(1, st, dr);
      return;
    }

    while(sum[ st ][ 0 ] + sum[ dr ][ 0 ] > S)
      --dr;
    while(sum[ st ][ 0 ] + sum[ dr ][ 0 ] < S)
      ++st;
  }

  printSolution(-1,0,0);
}

int main()
{
  readValues();

  setInitial();

  quickSort(1, N * N * N);

  binSearch();

  fclose(fin);
  fclose(fout);

  return 0;
}