Cod sursa(job #175063)

Utilizator alecmanAchim Ioan Alexandru alecman Data 9 aprilie 2008 15:53:53
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define INPUT "loto.in"
#define OUTPUT "loto.out"
#define pb push_back
#define NMAX 101
#define DMAX 1000001

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

int N;

long S, cont;
vector<long> nr(NMAX);
vector<long> value(DMAX);
vector<long> val(DMAX);

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

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

void setInitial()
{
  cont = 0;

  for(int i = 0; i < N; ++i)
    for(int j = 0; j < N; ++j)
      for(int k = 0; k < N; ++k)
      {
        value[ cont ] = nr[ i ] + nr[ j ] + nr[ k ];
	val[ cont ] = cont;
	++cont;
      }
}

void printSolution(long valor)
{
  long Cont;

  if(valor != -1)
  {
    Cont = 0;

    while(valor >= N * N)
    {
      valor -= N * N;
      ++Cont;
    }

    fprintf(fout, "%ld ", nr[ Cont ]);

    Cont = 0;

    while(valor >= N)
    {
      valor -= N;
      ++Cont;
    }

    fprintf(fout, "%ld ", nr[ Cont ]);

    fprintf(fout, "%ld ", nr[ valor ]);
  }
  else
    fprintf(fout, "-1");
}

void binSearch()
{
  long left = 0, right = cont;
  int OK = 1;

  while( left < right && OK)
  {
    while(value[ left ] + value[ right ] > S )
      --right;
    while(value[ left ] + value[ right ] < S )
      ++left;

    if(value[ left ] + value[ right ] == S)
    {
      printSolution(val[ left ]);
      printSolution(val[ right ]);

      break;
    }
  }

  if(left >= right)
    printSolution(-1);

  fprintf(fout, "\n");
}

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

  while( l != m)
  {
    if( ( l < m && value[ l ] > value[ m ]) || ( l > m && value[ l ] < value[ m ]))
    {
      value[ l ] = value[ l ] + value[ m ];
      value[ m ] = value[ l ] - value[ m ];
      value[ l ] = value[ l ] - value[ m ];
      val[ l ] = val[ l ] + val[ m ];
      val[ m ] = val[ l ] - val[ m ];
      val[ l ] = val[ l ] - val[ m ];
      l = l + m;
      m = l - m;
      l = 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);
}

int main()
{
  readValues();

  setInitial();

//  val.resize(cont+1);

  /*sort(value.begin(), value.end());*/

  quickSort(0, cont);

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

  binSearch();
  
  fclose(fin);
  fclose(fout);
  
  return 0;
}