Cod sursa(job #116013)

Utilizator savimSerban Andrei Stan savim Data 17 decembrie 2007 16:55:47
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <stdio.h>
int p,q,m,n,s,i,j,k,o,w,gas;
int a[101];
int sum[1000001],b[1000001];
void inter(int p, int q)
{
	 k=0;
	 int r=(p+q)/2,x=p,y=r+1,t;
	 while (x<=r && y<=q)
	 {
		   k++;
		   if (sum[x]<sum[y])
		   {
			  b[k]=sum[x];
			  x++;
		   }
		   else
		   {
			   b[k]=sum[y];
			   y++;
		   }
	 }
	 while (x<=r)
	 {
		   k++;
		   b[k]=sum[x];
		   x++;
	 }
	 while (y<=q)
	 {
		   k++;
		   b[k]=sum[y];
		   y++;
     }
     k=0;
     for (t=p; t<=q; t++)
     {
         k++;
         sum[t]=b[k];
     }
}
void merge(int p,int q)
{
     int r=(p+q)/2;
	 if (p==q) return;
	 merge(p,r);
	 merge(r+1,q);
	 inter(p,q);
}
int main()
{
    
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    
    scanf("%d%d",&n,&s);
    for (i=1; i<=n; i++)
        scanf("%d",&a[i]);
        
    m=0;
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            for (k=1; k<=n; k++)
            {
                m++;
				sum[m]=a[i]+a[j]+a[k];
            }
	merge(1,m);
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            for (k=1; k<=n; k++)        
            {
				o=s-(a[i]+a[j]+a[k]);
                p=1;q=m;gas=0;
				if (sum[m]!=o && sum[1]!=o)
				while (p+1<q)
				{
					w=(p+q)/2;
					if (sum[w]==o)
					{
					   gas=1;
					   break;
					}
					else if (sum[w]>o) q=w;
						 else p=w;
				}
				else gas=1;
				if (gas)
                {
				   printf("%d %d %d ",a[i],a[j],a[k]);
                   for (i=1; i<=n; i++)
                       for (j=1; j<=n; j++)
                           for (k=1; k<=n; k++)
							   if (a[i]+a[j]+a[k]==o)
                               {
                                  printf("%d %d %d\n",a[i],a[j],a[k]);
                                  return 0;                              
                               }
                }
            }
    printf("-1\n");   
    return 0;    
}