Cod sursa(job #2627294)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 10 iunie 2020 12:57:30
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>

using namespace std;

const int N = 100, MOD = 666019;

int v[N + 1], s3[N * N * N + 1], lst[MOD], urm[MOD];

static int nr = 0;

bool exista(int x) {
  int r = x % MOD;
  for (int p = lst[r]; p != 0; p = urm[p])
    if (s3[p] == x)
      return true;
  return false;
} 

void adauga(int x) {
  if (exista(x))
    return;
  int r = x % MOD;
  s3[++nr] = x;
  urm[nr] = lst[r];
  lst[r] = nr;
}

void afis(int a, int b, int c, int s, int n, ostream& out) {
  int sa = a + b + c;
  int sc;
  for (int i = 0; i < n; i ++)
    for (int j = i; j < n; j ++)
      for (int k = j; k < n; k ++) {
        sc = v[i] + v[j] + v[k];
        if (s - sc == sa) {
          out << a << " " << b << " " << c << " ";
          out << v[i] << " " << v[j] << " " << v[k];
          return;
        }
      }
}

int main() {
  ifstream in("loto.in");
  ofstream out("loto.out");
  
  int n, s;
  in >> n >> s;
  for (int i = 0; i < n; i ++)
    in >> v[i];
  
  for (int i = 0; i < n; i ++)
    for (int j = i; j < n; j ++)
      for (int k = j; k < n; k ++)
        adauga(v[i] + v[j] + v[k]);
  
  for (int i = 0; i < n; i ++)
    for (int j = i; j < n; j ++)
      for (int k = j; k < n; k ++)
        if (exista(s - v[i] - v[j] - v[k])) {
          afis(v[i], v[j], v[k], s, n, out);
          return 0;
        }
  
  out << "-1";
  
  in.close();
  out.close();
  return 0;
}