Cod sursa(job #175171)

Utilizator alecmanAchim Ioan Alexandru alecman Data 9 aprilie 2008 17:29:16
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define INPUT "loto.in"
#define OUTPUT "loto.out"
#define NMAX 105
#define DMAX 1000005

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

int N;

long S, cont;
vector<long> nr( NMAX ), value( DMAX );
long left = 0, right;
int OK = 1, i, j, k;
long Cont, tmp;

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

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

void printSolution(long sum)
{
  if(sum != -1)
  {
    OK = 1;

    for( i = 0; i < N && OK; ++i)
      for( j = 0; j < N && OK; ++j)
	for( k = 0; k < N && OK; ++k)
          if(nr[ i ] + nr[ j ] + nr[ k ] == sum)
	  {
            fprintf(fout, "%ld %ld %ld ", nr[ i ], nr[ j ], nr[ k ]);
	    OK = 0;
	  }
  }
  else
    fprintf(fout, "-1");
}

void binSearch()
{
  right = cont;

  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(value[ left ]);
      printSolution(value[ right ]);

      break;
    }
  }

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

  fprintf(fout, "\n");
}

void setInitial()
{
  cont = 0;

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

int main()
{
  readValues();

  setInitial();

  value.resize(cont+1);

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

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