Cod sursa(job #2687398)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 19 decembrie 2020 23:33:20
Problema Loto Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <algorithm>
#include <fstream>
using namespace std;
int v[ 101 ], el[ 7 ], pozi, n, s, poz;
struct elemente{
    int nr, sum;
} suma[ 999999 ];

bool caut( int val ){
    int st = 0, dr = poz - 1, mij, sol = -1;
    while( st <= dr ){
        mij = ( st + dr ) >> 1;
        if( suma[ mij ].sum <= val ){
            sol = mij;
            st = mij + 1;
        } else dr = mij - 1;
    }
    if( sol == -1 || suma[ sol ].sum != val )
        return false;
    int num = suma[ sol ].nr;
    el[ pozi++ ] = v[ num % 100 ];
    num /= 100;
    el[ pozi++ ] = v[ num % 100 ];
    num /= 100;
    el[ pozi++ ] = v[ num % 100 ];
    return true;
}

bool cmp( elemente A, elemente B ){
    if( A.sum > B.sum )
        return false;
    return true;
}

int main()
{
    int i;
    ifstream cin( "loto.in" );
    cin >> n >> s;
    for( i = 0; i < n; i++ )
        cin >> v[ i ];
    cin.close();
    for( i = 0; i < n; i++ )
        for( int j = i; j < n; j++ )
            for( int k = j; k < n; k++ )
                if( ( suma[ poz ].sum = v[ i ] + v[ j ] + v[ k ] ) <= s )
                    suma[ poz++ ].nr = ( i * 100 + j ) * 100 + k;
    sort( suma, suma + poz, cmp );
    for( i = 0; i < n; i++ )
        for( int j = i; j < n; j++ )
            for( int k = j; k < n; k++ )
                if( caut( s - ( v[ i ] + v[ j ] + v[ k ] ) ) ){
                    el[ pozi++ ] = v[ i ];
                    el[ pozi++ ] = v[ j ];
                    el[ pozi++ ] = v[ k ];
                    i = j = k = n + 10;
                }
    if( i == n ){
        ofstream cout( "loto.out" );
        cout << "-1\n";
    } else {
        sort( el, el + pozi );
        ofstream cout( "loto.out" );
        for( i = 0; i < pozi; i++ )
            cout << el[ i ] << ' ';
        cout << '\n';
    }
    return 0;
}