Cod sursa(job #1069427)

Utilizator DGVanceaDragos Gabriel Vancea DGVancea Data 30 decembrie 2013 00:19:45
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>


using namespace std;

struct nr
{
    int a,b,c,sum;
} v[1000010];

int n,s,l;
int d[110];

int search(int x)
{
    int st=1,m,dr=l;

    while (st<=dr)
    {
        m=(st+dr)/2;

        if (v[m].sum==x) return m;
        else if (x<v[m].sum) dr=m-1;
        else st=m+1;
    }

    return 0;
}
void quicksort(int l, int r)
{
    int i,j,p;
    nr aux;
    i=l;
    j=r;
    p=v[(l+r)/2].sum;
    while (i<=j)
    {
        while (v[i].sum<p)
            i++;
        while (v[j].sum>p)
            j--;
        if (i<=j)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            i++;
            j--;
        }
    }
    if (l<j)
        quicksort(l,j);
    if (i<r)
        quicksort(i,r);
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);

    scanf("%d %d ",&n,&s);

    int i,j,k,x,p=0;

    for (i=1; i<=n; i++) scanf("%d ",&d[i]);

    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            for (k=1; k<=n; k++)
            {
                p++;
                v[++l].sum=d[i]+d[j]+d[k];
                v[l].a=d[i];
                v[l].b=d[j];
                v[l].c=d[k];
            }


    quicksort(1,p);

    for (i=1; i<=n; i++)
    {
        x=s-v[i].sum;
        int j=search(x);
        if (j)
        {
            printf("%d %d %d %d %d %d",v[i].a,v[i].b,v[i].c,v[j].a,v[j].b,v[j].c);

            return 0;

        }
    }

    printf("-1\n");

    return 0;
}