Cod sursa(job #179273)

Utilizator AlxCojocaru Alexandru Alx Data 15 aprilie 2008 19:29:38
Problema Loto Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <stdio.h>
int n,s,a[100],nr=0;
struct element
{
    int a,b,c,s;
};
element sum[1000000];
void qsort(int li,int ls)
{
    if (ls-li>1)
    {
        int i=li,j=ls,i1=0,j1=-1;
        while (i<j)
        {
            if (sum[i].s>sum[j].s)
            {
                element aux=sum[i];
                sum[i]=sum[j];
                sum[j]=aux;
                int a2=i1;
                i1=-j1;
                j1=-a2;
            }
            i+=i1;
            j+=j1;
        }
        qsort(li,i);
        qsort(i+1,ls);
    }
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d %d\n",&n,&s);
    int i,j,k;
    for (i=0;i<n;i++)
        scanf("%d ",&a[i]);
    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
            for (k=0;k<n;k++)
            if (a[i]+a[j]+a[k]<=s)
            {
                    sum[nr].a=a[i];
                    sum[nr].b=a[j];
                    sum[nr].c=a[k];
                    sum[nr].s=a[i]+a[j]+a[k];
                    nr++;
            }
    qsort(0,nr-1);
    i=0;
    j=nr-1;
    while (sum[i].s+sum[j].s!=s&&i<=j)
        if (s>sum[i].s+sum[j].s)
            i++;
        else
            j--;
    if (i<=j)
        printf("%d %d %d %d %d %d\n",sum[i].a,sum[i].b,sum[i].c,sum[j].a,sum[j].b,sum[j].c);
    else
        printf("-1\n");
    return 0;
}