Cod sursa(job #201867)

Utilizator mgntMarius B mgnt Data 4 august 2008 15:27:27
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <algorithm>
using namespace std ;

int const MAXN = 100 ;
int S ;
int N ;
int X [MAXN] ;
int M ;
int sum3 [ MAXN * MAXN * MAXN ] ;

void
output ( ostream & oStreamOut , int Z ) {
  int i , r , f ;
    for ( i = 0 ; i < N ; i ++ )
      for ( r = i ; r < N ; r ++ )
        for ( f = r ; f < N ; f ++ )
          if (  (X [i] + X [r] + X [f]) == Z ) {
            oStreamOut << X [i] << ' ' << X [r] << ' ' << X [f] ;
            return ;
          }
}

int
main ( ) {
  ifstream oStreamIn  ( "loto.in"  ) ;
  ofstream oStreamOut ( "loto.out" ) ;
  oStreamIn >> N >> S ;
  int i , r, f ;
  for ( i = 0 ; i < N ; i ++ ) {
    oStreamIn >> X [ i ] ;
  }
  M = 0 ;
  for ( i = 0 ; i < N ; i ++ )
    for ( r = i ; r < N ; r ++ )
      for ( f = r ; f < N ; f ++ )
        sum3 [ M ++ ] = X [ i ] + X [r] + X [f] ;
  make_heap ( & sum3 [0], & sum3 [M] ) ;
  sort_heap ( & sum3 [0], & sum3 [M] ) ;
  int Y = - 1 ;
  for ( i = 0 ; i< M ; i ++ )
    if ( binary_search(& sum3 [0], & sum3 [M] , S - sum3 [i] ) ) {
      Y = sum3 [ i ] ;
      break ;
    }
  if ( -1 == Y ) {
    oStreamOut << "-1\n" ;
    return 0 ;
  }
  output ( oStreamOut , Y ) ;
  oStreamOut << ' ' ;
  output ( oStreamOut , S - Y ) ;
  return 0 ;
}