Cod sursa(job #943834)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 26 aprilie 2013 15:56:32
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<fstream>
#include<vector>

using namespace std;

const int kmod = 366019;

class obj{
public:
  int x, y, z, key, sum;

  obj(){};

  obj(int x1, int y1, int z1){
    x = x1;
    y = y1;
    z = z1;
    key = (x + y + z) % kmod;
    sum = x + y + z;
  }
};

vector<obj> h[kmod];

int isthere(int sum){
  if(sum < 0)
    return 0;
  int key = sum % kmod;
  for(int i = 0; i < h[key].size(); ++i)
    if(h[key][i].sum == sum)
      return i + 1;
  return 0;
}

void add(obj A){
  h[A.key].push_back(A);
}

int main(){
  ifstream in("loto.in");
  ofstream out("loto.out");

  int n, s;
  in >> n >> s;

  int a[105];
  for(int i = 1; i <= n; ++i)
    in >> a[i];

  if(n <= 25){
    for(int i = 1; i <= n; ++i) for(int j = i; j <= n; ++j) for(int k = j; k <= n; ++k)
    for(int i2 = k; i2 <= n; ++i2) for(int j2 = i2; j2 <= n; ++j2) for(int k2 = j2; k2 <= n; ++k2)
    if(a[i] + a[j] + a[k] + a[i2] + a[j2] + a[k2] == s){
      out << a[i] << " " << a[j] << " " << a[k] << " " << a[i2] << " " << a[j2] << " " << a[k2];
      return 0;
    }
    out << "-1";
    return 0;
  }

  for(int i = 1; i <= n; ++i)
    for(int j = i; j <= n; ++j)
      for(int k = j; k <= n; ++k){
        obj t(a[i], a[j], a[k]);
        int z = isthere(s - t.sum), ks;
        ks = (s - t.sum) % kmod;
        if(z){
          --z;
          out << a[i] << " " << a[j] << " " << a[k] << " " << h[ks][z].x << " " << h[ks][z].y << " " << h[ks][z].z;
          return 0;
        }
        add(t);
      }

  out << "-1";
  return 0;
}