Cod sursa(job #1809318)

Utilizator cristinamateiCristina Matei cristinamatei Data 18 noiembrie 2016 20:21:12
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int M = 666019;
int n, nr, vf[1000002], urm[1000002], lst[M];
int s, a[103];

bool exista( int x )
{
    int p, r = x%M;
    p = lst[r];
    while( p != 0 )
    {
        if ( vf[p] == x )
            return true;
        p = urm[p];
    }
    return false;
}

void adauga( int x )
{
    if (exista(x)) return;
    int r = x%M;
    nr++;
    vf[nr] = x;
    urm[nr] = lst[r];
    lst[r] = nr;
}

void afisare( int x )
{
    int i, j, k;
    for ( i = 1; i <= n; i++ )
        for ( j = i; j <= n; j++ )
            for ( k = j; k<= n; k++ )
                if ( a[i] + a[j] + a[k] == x )
                {
                    out << a[i]<<' '<< a[j]<<' '<<a[k];
                    return;
                }
}

int main()
{
    in >> n >> s;
    int i, j, k;
    for ( i = 1; i <= n; i++ )
        in >> a[i];

    for ( i = 1; i <= n; i++ )
        for ( j = i; j <= n; j++ )
            for ( k = j; k <= n; k++ )
                adauga( a[i] + a[j] + a[k] );

    for ( i = 1; i <= n; i++ )
        for ( j = i; j <= n; j++ )
            for ( k = j; k <= n; k++ )
                if ( a[i] + a[j] + a[k] <= s && exista( s - a[i] - a[j] - a[k] ) == true )
                {
                    out << a[i] <<' '<< a[j] <<' '<< a[k] <<' ';
                    afisare( s - a[i] - a[j] - a[k] );
                    return 0;
                }
    out <<-1;
    return 0;
}