Cod sursa(job #1122526)

Utilizator gerd13David Gergely gerd13 Data 25 februarie 2014 18:40:21
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 100 ;
const int QMAX = 1000001 ;

int Binarysearch(int, int, int);
void Initializare();
void Rezolvare();


ifstream cin("loto.in") ;
ofstream cout("loto.out") ;

int S, N;
int V[NMAX] ;
int A[NMAX], B[NMAX], C[NMAX] ;
int sum[NMAX] ;
int cnt ;

inline void Initializare()
{
    cin >> N ;
    cin >> S ;
    for(int i = 1 ; i <= N ; ++ i)
        cin >> V[i] ;

    for(int i =1 ; i<= N ; ++ i)
        for(int j = i; j <= N ; ++ j)
            for(int k = j; k <= N ; ++ k)
            {
                ++ cnt ;
                sum[cnt] = V[i] + V[j] + V[k];
            }
}

int Binarysearch(int x, int st, int fn)
{
    int mij ;
    while(fn -1 > st)
    {
        mij = st+(fn - st) / 2 ;
        if(sum[mij] == x)
            return mij;
        if(sum[mij] < x)
            st = mij + 1 ;
        else
            fn = mij - 1 ;
    }
    if(sum[fn] == x)
        return fn ;
    if(sum[st] == x)
        return st ;
    else return -1 ;
}

inline void Rezolvare()
{

    int ok, poz, macar, macar2;
    ok = 1 ;
    sort(sum + 1, sum + cnt + 1) ;
    ok = 0 ;
    for(int i = 1; i <= cnt ; ++ i)
    {
        poz = Binarysearch(S - sum[i], 1, cnt);
        if(poz > 0)
        {
            ok = 1 ;
            macar = S - sum[i] ;
            macar2 = sum[i] ;
            break ;
        }
    }
    if(ok == 0)
    {
        cout << -1 << '\n' ;
        return;
    }
    for(int i =1 ; i<= N ; ++ i)
        for(int j = i; j <= N ; ++ j)
            for(int k = j; k <= N ; ++ k)
                if(macar == V[i] + V[j] + V[k])
                {
                    cout << V[i] << ' ' << V[j] << ' ' << V[k] << ' ' ;
                    break ;
                }
    for(int i =1 ; i<= N ; ++ i)
        for(int j = i; j <= N ; ++ j)
            for(int k = j; k <= N ; ++ k)
                if(macar2 == V[i] + V[j] + V[k])
                {
                    cout << V[i] << ' ' << V[j] << ' ' << V[k] << '\n' ;
                    break ;
                    return ;
                }


}


int main ()
{
    Initializare() ;
    Rezolvare() ;
    cin.close() ;
    cout.close() ;
    return 0;
}