Cod sursa(job #316169)

Utilizator warchildmdMihail Burduja warchildmd Data 18 mai 2009 17:54:44
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include<cstdio>
#define NMAX 101
#include<vector>
#define DIM 8192
using namespace std;

struct nod
{
    int x;
    int y;
    int z;
    nod(int _a, int _b, int _c) { x=_a; y=_b; z=_c;};
    nod(){};
};

int a[NMAX];
vector<nod> H[666013];
char ax[DIM+16];
int pz;

inline void cit(int &x)
{
            x=0;
            while((ax[pz]<'0' || ax[pz]>'9') && (ax[pz]!='-'))
                        if(++pz==DIM)fread(ax, 1, DIM, stdin), pz=0;
            int neg=0;
            if(ax[pz]=='-')
            {
                        neg=1;
                        if(++pz==DIM)fread(ax, 1, DIM, stdin),pz=0;
            }
            while(ax[pz]>='0' && ax[pz]<='9')
            {
                        x=x*10+ax[pz]-'0';
                        if(++pz==DIM)fread(ax,1, DIM, stdin),pz=0;
            }
            if(neg) x=-x;
}

vector<nod>::iterator find_value(int x, int y, int z)
{
    int h = (a[x]+a[y]+a[z]) % 666013;
    vector<nod>::iterator it;
    for (it = H[h].begin(); it != H[h].end(); ++it)
        if ((it->x == x)&&(it->y == y)&&(it->z == z))
            return it;
    return H[h].end();
}

void insert(int x, int y, int z)
{
    int h = (a[x]+a[y]+a[z]) % 666013;
    if(find_value(x,y,z)==H[h].end())
    H[h].push_back(nod(x,y,z));
}

/*void del(int v)
{
    int h;
    h=v%666013;
    vector<nod>::iterator it=find_value(v);
    if(it!=H[h].end())
    H[h].erase(it);
}*/

int find(int v)
{
    int h=v%666013;
    for(vector<nod>::iterator it=H[h].begin(); it != H[h].end(); ++it)
    if (a[it->x]+a[it->y]+a[it->z] == v) return 1;
    return 0;
}

int main()
{
    int N,S, sum;
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    cit(N);
    cit(S);
    int i,j,k;
    for(i=1;i<=N;i++)
    {
        cit(a[i]);
    }

    for(i=1;i<=N;i++)
    for(j=1;j<=N;j++)
    for(k=1;k<=N;k++)
    {
        insert(i,j,k);
    }
    int x, y, z;
    for(i=1;i<=N;i++)
    for(j=1;j<=N;j++)
    for(k=1;k<=N;k++)
    {
        sum=S-a[i]-a[j]-a[k];
        if(sum>=0)
        {
            if(find(sum))
            {
                for(x=1;i<=N;i++)
                for(y=1;j<=N;j++)
                for(z=1;k<=N;k++)
                if(a[x]+a[y]+a[z]==sum)
                {
                    printf("%d %d %d %d %d %d\n",a[i],a[j],a[k],a[x],a[y],a[z]);
                    return 0;
                }
            }
        }
    }
    printf("-1\n");
    return 0;
}