Cod sursa(job #2779303)

Utilizator KarinAAndrei Karina KarinA Data 3 octombrie 2021 12:33:42
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int P = 370003;
vector <int> h[370005];

int n,s,ok;
int v[105];

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

void adaug_hash(int x)
{
    int r=x%P;
    if(h[r].size()==0 || h[r][0]!=x)
        h[r].push_back(x);
}

bool cauta_hash(int x)
{
    int r=x%P;
    for(int i=0; i<h[r].size();i++)
        if(h[r][i]==x)
            return 1;
    return 0;
}

void cauta_suma(int x)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            for(int k=j;k<=n;k++)
                if(v[i]+v[j]+v[k]==x){
                    out<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
                    return;
                }
        }
    }
}

void solve()
{
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            for(k=j;k<=n;k++)
                adaug_hash(v[i]+v[j]+v[k]);
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            for(k=j;k<=n;k++)
            {
                int suma=v[i]+v[j]+v[k];
                int comp=s-suma;
                if(comp>0)
                {
                    if(cauta_hash(comp))
                    {
                        cauta_suma(comp);
                        ok=1;
                        out<<v[i]<<" "<<v[j]<<" "<<v[k]<<'\n';
                        return;
                    }
                }
            }
        }
    }
    out<<-1;
}

int main()
{
    read();
    solve();
    return 0;
}