Cod sursa(job #1480943)

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

const int MAXN = 100;


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

struct cvadrupl
{
    long long sum;
    int nr1;
    int nr2;
    int nr3;
};

vector <cvadrupl> 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 = s.size() - 1;

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

        if( s[ m ].sum == x )
            return m;

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

    return -1;
}

bool cmp(cvadrupl a, cvadrupl b)
{
    return a.sum < b.sum;
}

void solve()
{
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            for(int k = 1; k <= N; k++)
            {
                cvadrupl w;

                w.sum = numbers[ i ] + numbers[ j ] + numbers[ k ];
                w.nr1 = numbers[ i ];
                w.nr2 = numbers[ j ];
                w.nr3 = numbers[ k ];

                s.push_back( w );
            }

    sort(s.begin(),s.end(), cmp);

    int poz = -1, index;

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

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

    if( poz != -1 )
    {
        cout<<s[ poz ].nr1<<' '<<s[ poz ].nr2<<' '<<s[ poz ].nr3<<' ';
        cout<<s[ index ].nr1<<' '<<s[ index ].nr2<<' '<<s[ index ].nr3<<' ';
    }
    else cout<<-1;


}

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

    readData();
    solve();

    return 0;
}