Cod sursa(job #175035)

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

void readValues()
{
  long X;

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

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

void setInitial()
{
  long X;
  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 ];
}

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 = 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(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;
}