Cod sursa(job #1276546)

Utilizator LizzardStanbeca Theodor-Ionut Lizzard Data 26 noiembrie 2014 15:57:04
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <algorithm>
#define _NMAX 101
#define _SMAX 1000010
using namespace std;

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

struct subset {
    int a, b, c, s;
    subset() {}
    subset ( int x, int y, int z ) {
        a = x;
        b = y;
        c = z;
        s = a + b + c;
    }
} a[_NMAX];

int search ( int li, int ls, int x ) {
    if ( li > ls )
        return -1;
        
    int m = ( li + ls ) / 2;
    
    if ( a[m].s == x )
        return m;
        
    if ( a[m].s < x )
        return search ( m + 1, ls, x );
        
    return search ( li, m - 1, x );
}

bool cmp ( subset a, subset b ) {
    return a.s < b.s;
}

int main() {
    int n, s, q = 0, aux;
    int v[_NMAX];
    fin >> n >> s;
    
    for ( int i = 0; i < n; i++ )
        fin >> v[i];
        
    for ( int i = 0; i < n; i++ )
        for ( int j = i; j < n; j++ )
            for ( int k = j; k < n; k++ )
                a[q++] = *new subset ( v[i], v[j], v[k] );
                
    sort ( a, a + q, cmp );
    
    for ( int i = 0; i < q; i++ ) {
        aux = search ( 0, q - 1, s - a[i].s );
        
        if ( aux != -1 ) {
            fout << a[i].a << " " << a[i].b << " " << a[i].c << " " << a[aux].a << " " << a[aux].b << " " << a[aux].c;
            return 0;
        }
    }
    
    fout << -1;
    return 0;
}