Cod sursa(job #1480887)

Utilizator DorelBarbuBarbu Dorel DorelBarbu Data 3 septembrie 2015 12:45:54
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100;

vector <long long> sums;
vector <int> nr1, nr2, nr3;

int numbers[MAXN+1], N, S;

void readData()
{
    scanf("%d %d",&N,&S);

    for(int i = 1; i <= N; i++)
        scanf("%d",&numbers[ i ]);
}

int binSearch(long long x)
{
    int left = 0, right = sums.size() - 1;

    while( left <= right )
    {
        int m = ( left + right ) / 2;

        if( sums[ m ] == x )
            return m;

        if( x < sums[ m ] )
            right = m - 1;
        else
            left  = m + 1;
    }

    return -1;
}

void solve()
{
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            for(int k = 1; k <= N; k++)
            {
                sums.push_back( numbers[ i ] + numbers[ j ] + numbers[ k ] );
                nr1.push_back( numbers[ i ] );
                nr2.push_back( numbers[ j ] );
                nr3.push_back( numbers[ k ] );
            }

    sort(sums.begin(),sums.end());

    int poz = -1, index;

    for(int i = 0; i < sums.size(); i++)
    {
        poz = binSearch( S - sums[ i ] );

        if( poz != -1 )
        {
            index = i;
            break;
        }
    }

    if( poz == -1  )
        printf("%d",-1);
    else
        printf("%d %d %d %d %d %d", nr1[ index ], nr2[ index ], nr3[ index ], nr1[ poz ], nr2[ poz ], nr3[ poz ]);
}

int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);

    readData();
    solve();

    return 0;
}