Cod sursa(job #75784)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 5 august 2007 17:38:15
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <stdio.h>
long a[101];
long v[1000001],index[1000001];
long n,dim,l,baza,k;


void iofile(void)
{
        long long i;
        freopen("loto.in","r",stdin);
        freopen("loto.out","w",stdout);
        scanf("%ld%ld",&n,&k);
        baza=(n+1);
        for (i=1;i<=n;i++)
                {
                        scanf("%ld",&a[i]);
                }
        fclose(stdin);
}


void repair(long i)
{
        long l,r,max,aux;
        l=(i*2);
        r=l+1;
        max=i;
        if ((l<=dim)&&(v[l]>v[i]))
                {
                        max=l;
                }
        if ((r<=dim)&&(v[r]>v[max]))
                {
                        max=r;
                }
        if (max!=i)
                {
                        aux=v[i];
                        v[i]=v[max];
                        v[max]=aux;
                        aux=index[i];
                        index[i]=index[max];
                        index[max]=aux;
                        repair(max);
                }
}


void build_heap(void)
{
        long i;
        for (i=(n/2);i>=1;i--)
                {
                        repair(i);
                }
}


void heapsort(void)
{
        long i,aux;
        build_heap();
        for (i=n;i>=2;i--)
                {
                        aux=v[i];
                        v[i]=v[1];
                        v[1]=aux;
                        aux=index[i];
                        index[i]=index[1];
                        index[1]=aux;
                        dim--;
                        repair(1);
                }
}


void gen_perechi(void)
{
        long i,j,k;
        l=0;
        for (i=1;i<=n;i++)
                for (j=1;j<=n;j++)
                        for (k=1;k<=n;k++)
                                {
                                        l++;
                                        v[l]=a[i]+a[j]+a[k];
                                        index[l]=(baza*baza*i)+(baza*j)+k;
                                }
        dim=l;
}


void aflu_index(long x, long &p1,long &p2, long &p3)
{
        p1=(x % baza);
        x=x/baza;
        p2=(x % baza);
        x=x/baza;
        p3=(x % baza);
}


void cauta_sol(void)
{
        long st,dr,p1,p2,p3,p4,p5,p6;
        st=1;
        dr=l;
        while ((st<=dr)&&((v[st]+v[dr])!=k))
                {
                        if ((v[st]+v[dr])>k)
                                {
                                        dr--;
                                } else
                                {
                                        st++;
                                };
                }
        if (st<=dr)
                {
                        aflu_index(index[st],p1,p2,p3);
                        aflu_index(index[dr],p4,p5,p6);
                        printf("%ld %ld %ld %ld %ld %ld\n",a[p1],a[p2],a[p3],a[p4],a[p5],a[p6]);
                } else
                {
                        printf("%ld\n",-1);
                }
        fclose(stdout);
}


int main(void)
{
        iofile();
        gen_perechi();
        heapsort();
        cauta_sol();
        return 0;
}