Cod sursa(job #2255499)

Utilizator gabrielmGabriel Majeri gabrielm Data 7 octombrie 2018 10:41:56
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

// Valoarea maxima a unui numar de la loterie
#define MAX_NR 100000
// Valoarea maxima a unei sume de 3 numere
#define MAX_SUMA (3 * MAX_NR)

int v[100];
int n, s;

struct Suma {
  int suma, a, b, c;
} sume[MAX_SUMA];
int lg;

void citire() {
  ifstream in("loto.in");
  in >> n >> s;

  for (int i = 0; i < n; ++i) {
    in >> v[i];
  }
}

void adauga_suma(int a, int b, int c) {
  sume[lg++] = {
    a + b + c,
    a, b, c,
  };
}

int cauta_binar(int val, int st, int dr) {
  while (st < dr) {
    int mid = st + (dr - st) / 2;

    if (val < sume[mid].suma) {
      dr = mid - 1;
    } else if (val > sume[mid].suma) {
      st = mid + 1;
    } else {
      return mid;
    }
  }

  return -1;
}

int main() {
  citire();

  // In O(n^3) facem o lista cu toate sumele de 3 termeni
  // pe care le putem obtine
  for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
      for (int k = j; k < n; ++k) {
        adauga_suma(v[i], v[j], v[k]);
      }
    }
  }

  // Pentru a putea cauta binar sumele, le sortam in O(n log n)
  sort(sume, sume + lg, [] (const Suma& a, const Suma& b) {
    return a.suma < b.suma;
  });

  ofstream out("loto.out");

  // For-ul se executa de maxim `MAX_SUMA` ori, pentru o eficienta totala de
  // O(MAX_SUMA * log MAX_SUMA) = O(1)
  for (int k = 0; k < lg; ++k) {
      Suma curent = sume[k];
      int diferenta = s - curent.suma;

      // Cauta binar o suma care sa acopere diferenta, in O(log MAX_SUMA)
      int i = cauta_binar(diferenta, 0, lg);

      if (i != -1) {
        Suma gasit = sume[i];
        out << curent.a << ' ' << curent.b << ' ' << curent.c << ' '
          << gasit.a << ' ' << gasit.b << ' ' << gasit.c << '\n';
        return 0;
      }
  }

  out << -1 << '\n';
}