Cod sursa(job #2659548)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 17 octombrie 2020 00:02:54
Problema Loto Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
// Mihai Priboi

#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

struct treinr {
  int x1, x2, x3, s;
};

vector<treinr> myhash[MOD];

int v[100];

int adauga( int x1, int x2, int x3 ) {
  unsigned int n, i, s;
  int poz;
  s = x1 + x2 + x3;
  poz = s % MOD;
  i = 0;
  n = myhash[poz].size();
  while( i < n && myhash[poz][i].s != s ) i++;
  if( i == n ) {
    myhash[poz].push_back({x1, x2, x3, s});
  }
}

int cauta( int s ) {
  unsigned int n, i;
  int poz;
  poz = s % MOD;
  i = 0;
  n = myhash[poz].size();
  while( i < n && myhash[poz][i].s != s ) i++;
  if( i == n )
    return -1;
  return i;
}

int main() {
  FILE *fin, *fout;
  int n, s, i, x1, x2, x3, poz, sum;
  bool flag;
  fin = fopen( "loto.in", "r" );
  fscanf( fin, "%d%d", &n, &s );
  for( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );
  fclose( fin );
  //
  for( x1 = 0; x1 < n; x1++ ) {
    for( x2 = 0; x2 < n; x2++ ) {
      for( x3 = 0; x3 < n; x3++ ) {
        if( v[x1] + v[x2] + v[x3] <= s )
          adauga(v[x1], v[x2], v[x3]);
      }
    }
  }
  //
  flag = false;
  x1 = 0;
  while( x1 < n && flag == false ) {
    x2 = 0;
    while( x2 < n && flag == false ) {
      x3 = 0;
      while( x3 < n && flag == false ) {
        sum = v[x1] + v[x2] + v[x3];
        if( sum <= s ) {
          poz = cauta(s - sum);
          if( poz != -1 && sum + myhash[(s - sum) % MOD][poz].s == s )
            flag = true;
        }
        x3++;
      }
      x2++;
    }
    x1++;
  }
  x1--;
  x2--;
  x3--;
  fout = fopen( "loto.out", "w" );
  if( flag == true )
    fprintf( fout, "%d %d %d %d %d %d", v[x1], v[x2], v[x3], myhash[(s - sum) % MOD][poz].x1,
        myhash[(s - sum) % MOD][poz].x2, myhash[(s - sum) % MOD][poz].x3 );
  else
    fprintf( fout, "-1" );
  fclose( fout );
  return 0;
}