Cod sursa(job #300954)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 7 aprilie 2009 20:16:20
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
# include <stdio.h>
# include <stdlib.h>
int a[1000000],c[1000000],d[1000000],b[200],q1[1000000],q2[1000000],q3[1000000],p,p1,p2,s,i,j,k,ok=0,n,aux,q,m,x,ok1,ok2;
void sort (int i,int j)
{
if (a[i]>a[j])
{
aux=a[i];
a[i]=a[j];
a[j]=aux;

}
}
void interc (int i,int j,int mij)
{
q=i;
p=mij+1;
k=0;
while (q<=mij && p<=j)
{
if (a[q]<a[p])
{
d[k]=a[q];
k++;
q++;
}
else
{
d[k]=a[p];
k++;
p++;
}
}
while (q<=mij)
{
d[k]=a[q];
k++;
q++;
}
while (p<=j)
{
d[k]=a[p];
k++;
p++;
}
k=0;
for (q=i;q<=j;q++)
{
a[q]=d[k];
k++;
}


}
void divimp (int i,int j)
{
int mij;
if (j-i<=1)
sort (i,j);
else
{
mij=(i+j)/2;
divimp (i,mij);
divimp (mij+1,j);
interc (i,j,mij);
}
}


int main ()
{
freopen ("loto.in","r",stdin);
freopen ("loto.out","w",stdout);
scanf ("%i",&n);
scanf ("%i",&s);
for (i=1;i<=n;i++)
scanf ("%i",&b[i]);
q=1;
for (i=1;i<=n;i++)
for (j=i;j<=n;j++)
for (k=j;k<=n;k++)
{
a[q]=b[i]+b[j]+b[k];
c[q]=a[q];
q1[q]=b[i];
q2[q]=b[j];
q3[q]=b[k];
q++;
}
m=q-1;
divimp (1,m);
i=1;
j=m;
while (ok==0 && i<=j)
{
if (a[i]+a[j]==s)
{
p1=i;
p2=j;
ok=1;
}
if (a[i]+a[j]<s)
i++;
else
j--;
}

if (ok==1)
{
for (i=1;i<=m;i++)
{
if (ok1==0)
if (c[i]==a[p1])
{
if (ok2==1)
printf (" ");
ok1=1;
printf ("%i %i %i",q1[i],q2[i],q3[i]);
}
if (ok2==0)
if (c[i]==a[p2])
{
if (ok1==1)
printf (" ");
ok2=1;
printf ("%i %i %i",q1[i],q2[i],q3[i]);
}
}
}
else
printf ("-1");


return 0;
}