Cod sursa(job #1572358)

Utilizator claudiuarseneClaudiu Arsene claudiuarsene Data 18 ianuarie 2016 21:16:48
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <algorithm>

using namespace std ;

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

int v[102] , N , S , cnt_t ;
struct suma_de_3 {
    int a , b , c ;
    int suma ;
};
suma_de_3 t[1000005] ;
int rasp[10] ;

int comp ( suma_de_3 A , suma_de_3 B )
{
 return A.suma < B.suma ;
}
int main ()
{
 f >> N >> S ;
 for ( int i = 1 ; i <= N ; ++i )
    f >> v[i] ;
 sort ( v + 1 , v + N + 1 ) ;
 for ( int i = 1 ; i <= N ; ++i )
    for ( int j = i ; j <= N ; ++j )
        for ( int k = j ; k <= N ; ++k )
            if ( v[i] + v[j] + v[k] <= S )
                {
                 t[++cnt_t].suma = v[i] + v[j] + v[k] ;
                 t[cnt_t].a = v[i] ;
                 t[cnt_t].b = v[j] ;
                 t[cnt_t].c = v[k] ;
                }
 sort ( t + 1 , t + cnt_t + 1 , comp ) ;
 int gasit = 0 , memo1 , memo2 ;
 for ( int i = 1 ; i <= cnt_t && !gasit ; ++i )
    {
     int s = S - t[i].suma ;
     int st = 1 , dr = cnt_t ;
     while ( st <= dr )
        {
         int mijl = ( st + dr ) / 2 ;
         if ( t[mijl].suma == s )
            gasit = 1 , memo1 = i  , memo2 = mijl ;
         else
            if ( t[mijl].suma < s )
                st = mijl + 1 ;
            else
                dr = mijl - 1 ;
         if ( gasit )
            st = dr + 1 ;
        }
    }
 if ( !gasit )
    g << "-1" ;
 else
    g << t[memo1].a << " " << t[memo1].b << " " << t[memo1].c << " " << t[memo2].a << " " << t[memo2].b << " "  << t[memo2].c << " " ;

}