Cod sursa(job #3157067)

Utilizator vladimir.gavris.1Gavris Mihai Vladimir vladimir.gavris.1 Data 14 octombrie 2023 11:27:26
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

#define MAXN 100
#define MAXS MAXN * MAXN * MAXN


struct optiuni
{
    int s;
    int i1;
    int i2;
    int i3;
}   sume[ MAXS + 1 ];

int numere[ MAXN + 1 ];

bool c( optiuni x, optiuni y )
{
    return x.s < y.s;
}

int cautare_binara( int l, int r, int num )
{
    int gasit = 0, mid;
    while ( l <= r )
    {
        mid = ( l + r ) / 2;
        if( num <= sume[ mid ].s )
        {
            r = mid - 1;
            gasit = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    if( sume[ gasit ].s == num )
        return gasit;
    return -1;
}

int main()
{
    int n, sumafin, i, j, x, contor = 0, complement, gasit;
    in >> n >> sumafin;
    optiuni d;

    for( i = 1; i <= n; i++ )
    {
        in >> numere[ i ];
    }

    for( i = 1; i <= n; i++ )
    {
        for( j = 1; j <= n; j++ )
        {
            for( x = 1; x <= n; x++ )
            {
                contor++;
                d.s = numere[ i ] + numere[ j ] + numere[ x ];
                d.i1 = numere[ i ];
                d.i2 = numere[ j ];
                d.i3 = numere[ x ];
                sume[ contor ] = d;
            }
        }
    }

    sort( sume + 1, sume + 1 + contor, c );

    for( i = 1; i <= contor; i++ )
    {
        complement = sumafin - sume[ i ].s;
        gasit = cautare_binara( 1, contor, complement );

        if( sume[ gasit ].s == complement )
        {
            out << sume[ gasit ].i1 << " " << sume[ gasit ].i2 << " " << sume[ gasit ].i3 << " ";
            out << sume[ i ].i1 << " " << sume[ i ].i2 << " " << sume[ i ].i3;
            break;
        }
    }

    if( i > contor )
        out << -1;
    return 0;
}