Cod sursa(job #1302518)

Utilizator deea101Andreea deea101 Data 26 decembrie 2014 23:46:14
Problema Loto Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");

const int size=400000;
int a[200];

struct triple
{
    int a,b,c;
    triple() {a=-1; b=-1; c=-1;}
};

class Hashtable
{
    private:
        struct node
        {
            triple t;
			int sum, state;
            
            node () { state=0; }
        }v[size];
        
        int hash (int key)
        {
            return (key%size);
        }

    public:
        triple lookup (int key)
        {
            int h=hash(key); triple nothing;
            while(v[h].state!=0 && v[h].sum!=key)
            {
                h++;
                if(h==size) h=0;
            }
            
            if(v[h].sum==key) return v[h].t;
            else return nothing;
        }
        void insert(int a,int b,int c,int key)
        {
            int h=hash(key);
            while(v[h].state!=0 && v[h].sum!=key)
            {
                h++;
                if(h==size) h=0;
            }
            
            if( ! (v[h].state == 1) )
            {
                v[h].state=1;
                v[h].t.a=a; v[h].t.b=b; v[h].t.c=c;
                v[h].sum=key;
            }
        }
}H;

    int main()
    {
        int N,S;
        f>>N>>S;
        int i,j,k,stemp,sol=0;
        triple res;
        for(i=1;i<=N;i++) f>>a[i];

        for(i=1;i<=N && !sol; i++)
            for(j=1;j<=N && !sol; j++)
                for(k=1;k<=N && !sol; k++)
                {
                    stemp=a[i]+a[j]+a[k];
                    H.insert(a[i],a[j],a[k],stemp);
                    
                    res=H.lookup(S-stemp);
                    if(res.a!=-1) 
                    {
                        sol=1; g<<a[i]<<' '<<a[j]<<' '<<a[k]<<' '<<res.a<<' '<<res.b<<' '<<res.c;
                    }
                }
        if(!sol) g<<-1;
    }