Cod sursa(job #175022)

Utilizator alecmanAchim Ioan Alexandru alecman Data 9 aprilie 2008 15:05:39
Problema Loto Scor 0
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 pb push_back

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

int N;

long S;
vector<long> nr;
vector<long> value;

void readValues()
{
  long X;

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

  for(int i = 1; i <= N; ++i)
  {
    fscanf(fin, "%ld", &X);
    nr.pb(X);
  }
}

void setInitial()
{
  long X;

  for(int i = 0; i < N; ++i)
    for(int j = 0; j < N; ++j)
      for(int k = 0; k < N; ++k)
      {
        X = nr[ i ] + nr[ j ] + nr[ k ];
	value.pb(X);
      }
}

void printSolution(long val)
{
  long cont;

  if(val != -1)
  {
    cont = 0;

    while(val > N * N)
    {
      val -= N * N;
      ++cont;
    }

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

    cont = 0;

    while(val > N)
    {
      val -= N;
      ++cont;
    }

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

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

void binSearch()
{
  long left = 0, right = value.size();
  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(left + 1);
      printSolution(right + 1);

      break;
    }
  }

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

  fprintf(fout, "\n");
}

int main()
{
  readValues();

  setInitial();

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

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