Cod sursa(job #285873)

Utilizator lolopolololopolo lolopolo Data 23 martie 2009 09:04:06
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<fstream>

using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

struct sum { long x,y,z,su;
           } s[1000001];
long a[101],n,suma,k,ok,l;

void quick(long x,long y)
{   long i,j,p;
    sum aux;
	if(x<y)
	{	i=x-1;
		j=y+1;
		p=s[(x+y)/2].su;
		while(i<j)
		{	do i++; while(s[i].su<p);
			do j--; while(s[j].su>p);
			if(i<j) {  aux=s[i];
				       s[i]=s[j];
				       s[j]=aux;
				     }
		}
		quick(x,i-1);
		quick(j+1,y);
	}
}

void citire()
{    int i,j,k;
     fin>>n>>suma;
     for(i=1;i<=n;i++)
         fin>>a[i];
     for(i=1;i<=n;i++)
         for(j=i;j<=n;j++)
             for(k=j;k<=n;k++) 
             {      s[++l].su=a[i]+a[j]+a[k];
                    s[l].x=a[i];
                    s[l].y=a[j];
                    s[l].z=a[k];
             }
     quick(1,l);
}            

int main()
{    long i,st,d,p,m,i1,i2;
     citire();
     for(i=1;i<=l;i++)
     {       p=suma-s[i].su;
             st=i;
             d=l;
             while(st<=d)
             {     m=(st+d)/2;
                   if(s[m].su>p) d=m-1;
                     else if(s[m].su<p)  st=m+1;
                         else break;
             }
             if(st<=d) {   ok=1;
                          i1=i;
                          i2=m;
                          break;
                       }
     }
     if(!ok) fout<<-1;
      else fout<<s[i1].x<<" "<<s[i1].y<<" "<<s[i1].z<<" "<<s[i2].x<<" "<<s[i2].y<<" "<<s[i2].z;
     fin.close();
     fout.close();
     return 0;
}