Cod sursa(job #1317953)

Utilizator andrettiAndretti Naiden andretti Data 15 ianuarie 2015 13:53:35
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define maxn 105
#define MOD 666013
using namespace std;

struct trio{int sum,x,y,z;};

int n,S,ok,nr;
int a[maxn];
vector< trio > h[MOD];

int hash_key(int val){
    return val%MOD;
}

void hash_insert(int val,int x1,int x2,int x3)
{
    int k=hash_key(val);
    for(unsigned int i=0;i<h[k].size();i++)
     if(h[k][i].sum==val) return;

    h[k].pb( {val,x1,x2,x3} );
}

trio hash_search(int val)
{
    int k=hash_key(val);
    for(unsigned int i=0;i<h[k].size();i++)
     if(h[k][i].sum==val) return {val,h[k][i].x,h[k][i].y,h[k][i].z};

    return {0,0,0,0};
}

void read()
{
    scanf("%d%d",&n,&S);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
}

void solve()
{
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      for(int k=1;k<=n;k++)
       if(a[i]+a[j]+a[k]<=S)
        hash_insert(a[i]+a[j]+a[k],a[i],a[j],a[k]);

    trio cnt;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      for(int k=1;k<=n;k++)
       if(S-a[i]-a[j]-a[k]>0)
       {
           cnt=hash_search(S-a[i]-a[j]-a[k]);
           if(cnt.sum!=0)
           {
               printf("%d %d %d %d %d %d",a[i],a[j],a[k],cnt.x,cnt.y,cnt.z);
               return;
           }
       }
    printf("-1");
}

int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);

    read();
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}