Cod sursa(job #609975)
Utilizator | Data | 24 august 2011 10:24:07 | |
---|---|---|---|
Problema | Loto | Scor | 100 |
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=(l/2);i>=1;i--)
{
repair(i);
}
}
void heapsort(void)
{
long i,aux;
build_heap();
for (i=l;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=i;j<=n;j++)
for (k=j;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;
}