Cod sursa(job #175043)

Utilizator alecmanAchim Ioan Alexandru alecman Data 9 aprilie 2008 15:31:41
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 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 ];

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++ ] = 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 ] > sum[ m ]) || ( l > m && sum[ l ] < sum[ m ] ) )
    {
      exchange( sum[ l ], sum[ m ]);
/*      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)
{
  int cont;

  if(code == 1)
  {
    cont = 1;

    while(fValue > N * N)
    {
      fValue -= N * N;
      ++cont;
    }
    fprintf(fout, "%ld ", a[ cont ]);

    cont = 1;

    while(fValue > N )
    {
      fValue -= N;
      ++cont;
    }
    fprintf(fout, "%ld ", a[ cont ]);

    fprintf(fout, "%ld ", a[fValue ]);

    cont = 1;

    while(sValue > N * N)
    {
      sValue -= N * N;
      ++cont;
    }
    fprintf(fout, "%ld ", a[ cont ]);

    cont = 1;

    while(sValue > N )
    {
      sValue -= N;
      ++cont;
    }
    fprintf(fout, "%ld ", a[ cont ]);

    fprintf(fout, "%ld ", a[ sValue ]);
  }
  else
    fprintf(fout, "-1\n");
}

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

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

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

  printSolution(-1,0,0);
}

int main()
{
  readValues();

  setInitial();

  for(vector<long>::iterator it = nr.begin(); it != nr.end(); ++it)
    fprintf(stderr, "%ld ", *it);

  quickSort(1, N * N * N);

  binSearch();

  fclose(fin);
  fclose(fout);

  return 0;
}