Cod sursa(job #1189875)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 23 mai 2014 19:04:44
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 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;
    bool test=0;
    nod k;
    fin>>n>>S;
    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<=5)
        {
            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++;
        }
    len=H[S%modulo].size();
    aux=6;test=1;
    while (aux>0 && test)
        {
            test=0;
            len=H[S%modulo].size();
            for (j=0;j<len;j++)
                if (H[S%modulo][j].pasi==aux && H[S%modulo][j].val==S)
                    {
                        test=1;
                        sol[++sol[0]]=H[S%modulo][j].backin;
                        S-=sol[sol[0]];
                        j=len+1;
                    }
            aux--;
        }
    if (aux==0)
        {
            sort(sol+1,sol+sol[0]+1);
            for (i=1;i<=sol[0];i++) fout<<sol[i]<<" ";
        }
    else fout<<"-1";
    fout<<"\n";
    return 0;
}