Cod sursa(job #1189890)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 23 mai 2014 20:18:53
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.13 kb
#include<fstream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

struct nod
{
    int val,pasi,backin;
};

const int modulo=1000007;

int n,S,a[105],sol[10];
vector<nod>H[modulo];

int main()
{
    int i,indice,j,len,l,p,aux,xl,yl,xr,yr,SL,SK;
    bool test=0;
    nod k;
    fin>>n>>S;
    xl=yl=xr=yr=SL=SK=-1;
    for (i=1;i<=n;i++)
        {
            fin>>a[i];
            k.val=a[i];
            k.pasi=1;
            k.backin=a[i];
            H[a[i]%modulo].push_back(k);
        }
    sort(a+1,a+n+1);
    indice=1;
    while (indice<=2)
        {
            for (i=0;i<=modulo-1;i++)
                {
                    len=H[i].size();
                    for (j=0;j<len;j++)
                        if (H[i][j].pasi==indice)
                            for (l=1;l<=n;l++)
                            {
                                aux=(H[i][j].val+a[l])%modulo;
                                test=0;
                                for (p=0;p<H[aux].size() && !test;p++)
                                    if (H[aux][p].pasi==indice+1 && H[aux][p].val==H[i][j].val+a[l])
                                        {
                                            p=H[aux].size()+1;
                                            test=1;
                                        }
                                if (!test)
                                    {
                                        k.pasi=indice+1;
                                        k.val=H[i][j].val+a[l];
                                        k.backin=a[l];
                                        H[aux].push_back(k);
                                        p=H[aux].size()+1;
                                    }
                            }

                }
            indice++;
        }
    for (i=0;i<=modulo-1;i++)
        {
           len=H[i].size();
           for (j=0;j<len;j++)
                if (H[i][j].pasi==3 && H[i][j].val<=S)
                    {
                        aux=S-H[i][j].val;
                        p=aux%modulo;
                        for (l=0;l<H[p].size();l++)
                            if (H[p][l].pasi==3 && H[p][l].val==aux)
                                {
                                    xl=i;
                                    yl=j;
                                    xr=p;
                                    yr=l;
                                    SL=H[i][j].val;
                                    SK=H[p][l].val;
                                    l=H[p].size()+1;
                                    p=len+1;
                                    i=modulo;
                                }
                    }
        }

    if (SL!=-1)
        {
           aux=3;test=1;
            while (aux>0 && test)
                {
                    test=0;
                    len=H[SL%modulo].size();
                    for (j=0;j<len;j++)
                        if (H[SL%modulo][j].pasi==aux && H[SL%modulo][j].val==SL)
                            {
                                test=1;
                                sol[++sol[0]]=H[SL%modulo][j].backin;
                                SL-=sol[sol[0]];
                                j=len+1;
                            }
                    aux--;
                }
            aux=3;test=1;
            while (aux>0 && test)
                {
                    test=0;
                    len=H[SK%modulo].size();
                    for (j=0;j<len;j++)
                        if (H[SK%modulo][j].pasi==aux && H[SK%modulo][j].val==SK)
                            {
                                test=1;
                                sol[++sol[0]]=H[SK%modulo][j].backin;
                                SK-=sol[sol[0]];
                                j=len+1;
                            }
                    aux--;
                }
            sort(sol+1,sol+sol[0]+1);
            for (i=1;i<=sol[0];i++) fout<<sol[i]<<" ";
        }
    else fout<<"-1";
    fout<<"\n";
    return 0;
}