Cod sursa(job #220545)

Utilizator ghitza_2000Stefan Gheorghe ghitza_2000 Data 11 noiembrie 2008 15:23:42
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define MAX_N 102

long N,S,A[MAX_N];
int Nr;

struct lot{long a,b,c,s;} V[MAX_N*MAX_N*MAX_N];


void citire()
{
    scanf("%ld %ld",&N,&S);

    for(int i=0; i<N; i++)
        scanf("%ld",A+i);
}


struct comp
{
    bool operator() (const lot &a, const lot &b) const
    {
        return (a.s < b.s);
    }
} ;


int main()
{
    freopen("loto.in","rt",stdin);
    freopen("loto.out","wt",stdout);
    citire();

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            for(int k=0; k<N; k++)
            {
                V[Nr].s = A[i] + A[j] + A[k];
                V[Nr].a = A[i], V[Nr].b = A[j], V[Nr++].c = A[k];
            }

    sort(V,V+Nr,comp());


    for(int i=0; i< Nr; i++)
    {
        int li = i, lf = Nr-1,m;

        if(V[i].s + V[i].s > S) continue;
        while(li <= lf)
        {
            m = (li+lf) >> 1;

            if(V[m].s + V[i].s == S)
            {
                printf("%ld %ld %ld %ld %ld %ld\n",V[i].a,V[i].b,V[i].c,V[m].a,V[m].b,V[m].c);
                return 0;
            }

            if(V[m].s + V[i].s > S)
                lf = m-1;

            else
                li = m+1;
        }
    }

    printf("-1\n");
}