Cod sursa(job #1182264)
Utilizator | Data | 5 mai 2014 17:26:20 | |
---|---|---|---|
Problema | Loto | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.89 kb |
#include <iostream>
#include <fstream>
using namespace std;
long a[101];
long v[1000001],index[1000001];
long n,dim,l,baza,k;
ifstream f("loto.in");
ofstream g("loto.out");
void iofile()
{
long long i;
f>>n>>k;
baza=(n+1);
for (i=1;i<=n;i++)
f>>a[i];
f.close();
}
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()
{
long i;
for (i=(l/2);i>=1;i--)
repair(i);
}
void heapsort()
{
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()
{
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);
g<<a[p1]<<"\t"<<a[p2]<<"\t"<<a[p3]<<"\t"<<a[p4]<<"\t"<<a[p5]<<"\t"<<a[p6];
}
else
g<<"-1";
g.close();
}
int main()
{
iofile();
gen_perechi();
heapsort();
cauta_sol();
return 0;
}