Cod sursa(job #165272)

Utilizator nimeniaPaul Grigoras nimenia Data 25 martie 2008 19:49:46
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>

long v[105],n,ns=1;
long a[1000020];
long drum[1000020],drum_aux;
int auxxx[10];

int poz(long li,long ls){
	long i=li,j=ls,t;int mod=1;
	while (i!=j){
		  if (a[i]>a[j]){
			 t=a[i],a[i]=a[j],a[j]=t;
			 t=drum[i],drum[i]=drum[j],drum[j]=t;
			 mod=(mod+1)%2;
			 }
		  if (mod==0) i++;
		  else j--;
		  }
	return i;

}

void qsort(long li, long ls){
	if (li<ls){
		long k=poz(li,ls);
		qsort(li,k);
		qsort(k+1,ls);
	}
}


int gasit(long ax){
   long li=1,ls=ns,m;
   if (a[ls]==ax) return ls;
   else {
   while (li!=ls){
	m=(li+ls)/2;
	if (ax>a[m]) li=m+1;
	else if (ax<a[m]) ls=m;
	else if (ax==a[m]) return m;
   }}
   return 0;

}



int main(){
	long j,k,q,aux,s;
	freopen ("loto.in", "r",stdin);
	freopen ("loto.out","w",stdout) ;
	scanf("%ld%ld",&n,&s);
	long i;
	for(i=1;i<=n;i++) scanf("%ld",v+i);
	for(i=1;i<=n;i++)for(j=i;j<=n;j++)for(q=j;q<=n;q++)a[ns++]=v[i]+v[j]+v[q],drum[ns-1]=i+j*100+q*10000;
	ns--;
	qsort(1,ns);


    v[0]=v[n];
	int gata=0;
	for (i=1;i<=ns && !gata;i++)
		if (a[i]!=a[i-1]){
			k=gasit(s-a[i]);
			if (k)
				{gata=1;
				 drum_aux=drum[i];
		         for (j=0;j<3;j++) auxxx[j]=drum[i]%100, drum[i]/=100;
         
				 drum[i]=drum_aux;
 		         for (j=3;j<6;j++) auxxx[j]=drum[k]%100, drum[k]/=100;

                 for(j=0;j<6;j++) printf("%ld ",v[auxxx[j]]);
				}

		}
	if (!gata) printf("-1");

	return 0;
    
    
                     
    
}