Cod sursa(job #2580948)

Utilizator andaraluca2001Anda Epure andaraluca2001 Data 14 martie 2020 13:23:19
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("loto.in");
ofstream out("loto.out");
const int N=1000006;
const int K=666019;
int val[N], urm[N],lst[N],nr;
int n,s,v[101];
bool ok;

bool apartine(int x)
{
    if (x < 0) return false;
    int c=x%K;
    for(int p=lst[c]; p!=0; p=urm[p])
    {
        if(val[p]==x)
            return true;
    }

    return false;
}

void adauga(int x)
{
    if(apartine(x))
        return;
    if (x < 0) return;
    int c=x%K;
    val[++nr]=x;
    urm[nr]=lst[c];
    lst[c]=nr;
}

int main()
{
    in>>n>>s;
    for(int i=1; i<=n; i++)
        in>>v[i];

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            for(int k=1; k<=n; k++)
            {
                int suma=v[i]+v[j]+v[k];
                adauga(suma);
            }
        }
    }

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            for(int k=1; k<=n; k++)
            {
                int suma=v[i]+v[j]+v[k];
                bool verif=apartine(s-suma);
                if(verif)
                {
                    out<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
                    for(int l=1; l<=n; l++)
                    {
                        for(int r=1; r<=n; r++)
                        {
                            for(int t=1; t<=n; t++)
                            {
                                if(v[l]+v[r]+v[t]==s-suma)
                                {
                                    out<<v[l]<<" "<<v[r]<<" "<<v[t];
                                    exit(0);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    out<<"-1";
    return 0;
}