Pagini recente » Cod sursa (job #586880) | Cod sursa (job #2413861) | Cod sursa (job #1917461) | Cod sursa (job #1186495) | Cod sursa (job #336821)
Cod sursa(job #336821)
#include<fstream.h>
#define nmax 101
int n,sw;
long v[nmax],s,s3[nmax*nmax*nmax],dim,r[7],s1,s2;
void cit()
{
ifstream fin("loto.in");
fin>>n>>s;
for(int i=1;i<=n;i++)
fin>>v[i];
fin.close();
}
void constr_sume_3()
{
int i,j,k;
dim=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
s3[++dim]=v[i]+v[j]+v[k];
}
long divide(long p,long q)
{
long x=s3[p];
long st=p,dr=q;
while(st<dr)
{
while(st<dr&&s3[dr]>=x)
dr--;
s3[st]=s3[dr];
while(st<dr&&s3[st]<=x)
st++;
s3[dr]=s3[st];
}
s3[st]=x;
return st;
}
void Qsort(long p,long q)
{
long m=divide(p,q);
if(m-1>p)
Qsort(p,m-1);
if(m+1<q)
Qsort(m+1,q);
}
long caut_binar(long p,long q)
{
if(p>q)
return -1;
long m=(p+q)/2;
if(s3[m]==s2)
return m;
if(s3[m]<s2)
return caut_binar(m+1,q);
return caut_binar(p,m-1);
}
void rez()
{
sw=0;//Consideram ca nu exista doua sume s1 si s2 a i s1+s2=s
long m;
int i,j,k;
for(i=1;i<=dim&&sw==0;i++)
{
s1=s3[i];
s2=s-s1;
m=caut_binar(1,dim);
if(m!=-1)
sw=1;
}
if(sw==1)
{
int g1=0,g2=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
{
int sum=v[i]+v[j]+v[k];
if(sum==s1)
{
r[1]=v[i]; r[2]=v[j]; r[3]=v[k];
g1=1;
}
if(sum==s2)
{
r[4]=v[i]; r[5]=v[j]; r[6]=v[k];
g2=1;
}
}
}
}
void afis()
{
ofstream fout("loto.out");
if(sw==1)
for(int i=1;i<=6;i++)
fout<<r[i]<<" ";
else
fout<<-1;
fout<<'\n';
fout.close();
}
int main()
{
cit();
constr_sume_3();
Qsort(1,dim);
rez();
afis();
return 0;
}