Cod sursa(job #1196965)

Utilizator Vladinho97Iordan Vlad Vladinho97 Data 10 iunie 2014 01:05:59
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include<cstdio>
#include<stdlib.h>
#include<vector>
#define MOD 666013
#define nmax 109
#define MAX 666200
using namespace std;
struct nod
{
    int val;
    int n1,n2,n3;
    nod* urm;
};
nod* v[MAX];
int val[nmax];
bool a[MAX];
vector <int>pos;
void insert(int x,int i,int j,int k)
{
    nod* aux = (nod*) malloc(sizeof(nod));
    aux->val =x;
    aux -> n1=i;
    aux -> n2=j;
    aux -> n3=k;
    aux ->urm= NULL;
    int rand= x%MOD;
    if(v[rand]==NULL)
    {
        v[rand]=aux;
        return;
    }
    nod* ptr = v[rand];
    nod* anterior;
    while(ptr!=NULL)
    {
        anterior=ptr;
        ptr=ptr->urm;
    }
    anterior->urm = aux;
    return;
}
bool cautare(int x)
{
    int rand= x % MOD;
    if(v[rand]==NULL)
        return false;
    nod* ptr = v[rand];
    while(ptr!=NULL)
    {
        if(ptr->val==x)
        {
            printf("%d %d %d ",val[ptr->n1],val[ptr->n2],val[ptr->n3]);
            return true;
        }
    }
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    int i,j,k,n,s;
    scanf("%d%d",&n,&s);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
            {
                if(a[(val[i]+val[j]+val[k])%MOD]==false)
                {
                    a[(val[i]+val[j]+val[k])%MOD]=true;
                    pos.push_back((val[i]+val[j]+val[k])%MOD);
                }
                insert(val[i]+val[j]+val[k],i,j,k);
            }
    int lung=pos.size();
    for(i=0;i<lung;++i)
    {
        nod* ptr= (nod*) malloc(sizeof(nod));
        ptr= v[pos[i]];
        while(ptr!=NULL)
        {
            if(cautare(s-(ptr->val))==true)
            {
                printf("%d %d %d\n",val[ptr->n1],val[ptr->n2],val[ptr->n3]);
                return 0;
            }
            ptr=ptr->urm;
        }
    }
    printf("-1\n");
    return 0;
}