Cod sursa(job #1764987)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 26 septembrie 2016 10:13:34
Problema Loto Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia1-hashuri.rabinkarp Marime 1.5 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define MOD 10007
using namespace std;
 
int N,v[1005],F,Sum,i,j,k;
bool found=false;
struct Hash
{
    int x,y,z,S;
}C;
struct OUT
{
    int x,y,z;
    bool b;
}Out,out;
vector <Hash> H[MOD];
int f(int val)
{
    return abs(val%MOD);
}
void Add(int x1,int x2,int x3)
{
    F=f(v[x1]+v[x2]+v[x3]);
    C.x=x1;
    C.y=x2;
    C.z=x3;
    C.S=v[x1]+v[x2]+v[x3];
    H[F].push_back(C);
}
OUT Search(int val)
{
    F=f(val);
    out.b=false;
    for(i=0;i<H[F].size();i++)
        if(H[F][i].S==val)
        {
            out.b=true;
            out.x=H[F][i].x;
            out.y=H[F][i].y;
            out.z=H[F][i].z;
            return out;
        }
    return out;
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&N,&Sum);
    for(int i=1;i<=N;i++)
        scanf("%d",&v[i]);
    sort(v+1,v+1+N);
    for (i=1;i<=N;i++)
        for (j=1;j<=N;j++)
            for (k=1;k<=N;k++)
                Add(i,j,k);
    for (int p=0;p<=MOD;p++)
    {
        if(found)
            break;
        for(int q=0;q<H[p].size();q++)
        {
            Out=Search(Sum-H[p][q].S);
            if (Out.b)
            {
                printf("%d %d %d %d %d %d",v[H[p][q].x],v[H[p][q].y],v[H[p][q].z],v[Out.x],v[Out.y],v[Out.z]);
                found=true;
                break;
            }
        }
    }
    if(!found)
        printf("-1");
    return 0;
}