Cod sursa(job #1035703)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 18 noiembrie 2013 19:19:21
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int v[101], sume[1000001];

void getn( int s, FILE *g, int n ) {
    int gasit = 1;

    for( int a = 0 ; a < n && gasit ; ++a )
        for( int b = a ; b < n && gasit ; ++b )
            for( int c = b ; c < n && gasit ; ++c )
                if( v[a] + v[b] + v[c] == s ) {
                    gasit = 0;
                    fprintf( g, "%d %d %d ", v[a], v[b], v[c] );
                }

}


int main () {

    FILE *f, *g;
    f = fopen( "loto.in", "r" );
    g = fopen( "loto.out", "w" );

    int n, s, sum, start, stop, nr = 0, gasit = 1, p;

    fscanf( f, "%d%d", &n, &s );

    for( int i = 0 ; i < n ; ++i )
        fscanf( f, "%d", &v[i] );

    for( int i = 0 ; i < n ; ++i )
        for( int j = i ; j < n ; ++j )
            for( int k = j ; k < n ; ++k ) {
                sume[nr] = v[i] + v[k] + v[j];
                ++nr;
            }

   // cout<<nr<<endl;
    sort(sume, sume + nr );

    for( int i = 0 ; i < nr && gasit ; ++i ) {
       // cout<<sume[i]<<" ";
        sum = s - sume[i];
        start = 0;

        p = ( 1 << 20 );
        while( p ) {
            stop = start + p;
            if( stop < nr && sume[stop] <= sum )
                start = stop;

            p >>= 1;
        }

        if( sume[start] == sum )
            gasit = 0;
    }

    if( gasit == 1 )
        fprintf( g, "-1" );

    else {
        getn( s - sum, g, n );
        getn( sum, g, n );
    }

    fclose( f );
    fclose( g );

    return 0;
}