Cod sursa(job #823593)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 25 noiembrie 2012 12:35:33
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<cstdio>
#include<vector>
#define MOD 666013
using namespace std;
vector<pair<int,int> > HASH[MOD+10];
vector<int>SOL[400010];
int n,i,S,A[110],SUM,s,cnt,ok,B,C,j,k;
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&S);
    for(i=1;i<=n;i++)
        scanf("%d",&A[i]);
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++)
            {
                SUM=A[i]+A[j]+A[k];
                s=SUM%MOD;
                ok=1;
                for(vector<pair<int,int> >::iterator it=HASH[s].begin();it!=HASH[s].end();it++)
                    if(it->first==SUM){ok=0;break;}
                if(ok)
                {
                    HASH[s].push_back(make_pair(SUM,++cnt));
                    SOL[cnt].push_back(A[i]);
                    SOL[cnt].push_back(A[j]);
                    SOL[cnt].push_back(A[k]);
                }
                //introdu^
                //cauta
                if(SUM>S)continue;
                C=S-SUM;
                s=C%MOD;
                for(vector<pair<int,int> >::iterator it=HASH[s].begin();it!=HASH[s].end();it++)
                    if(it->first==C)
                    {
                        printf("%d %d %d ",A[i],A[j],A[k]);
                        cnt=it->second;
                        for(vector<int>::iterator jt=SOL[cnt].begin();jt!=SOL[cnt].end();jt++)
                            printf("%d ",*jt);
                        return 0;
                    }
            }
    printf("-1\n");
    return 0;
}