Cod sursa(job #146433)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 1 martie 2008 18:16:29
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>   
#define N 100   
#define M 1000000
int n,x[N],v[M],p[M],num,S;
int part(int s,int d){
	int i,j,aux,piv;
	i=s-1;
	j=d+1;
	piv=v[(s+d)/2];
	while(1){
		do{
			++i;
		}while(v[i]<piv);
		do{
			--j;
		}while(v[j]>piv);
		if(i<j){
			aux=v[i];
			v[i]=v[j];
			v[j]=aux;
			aux=p[i];
			p[i]=p[j];
			p[j]=aux;
		}
		else
			return j;
	}
}   
void sort(int s,int d){
	int m;
	if(s<d){
		m=part(s,d);
		sort(s,m);
		sort(m+1,d);
	}
}
int caut(int val){
	int s,d,m;
	s=1;
	d=num;
	while(s<=d){
		m=(s+d)/2;
		if(v[m]==val)
			return m;
		else
		{
			if(v[m]>val)
				d=m-1;
			else
				s=m+1;
		}
	}
    return 0;
}
void poz(int p){
	int c,r;
	c=p/(n*n);   
    r=p%(n*n);
	printf("%d ",x[c+(r!=0)]);
	if(r==0)
		printf("%d %d ",x[n],x[n]);
	else{
		p=r;
		c=p/n;
		r=p%n;
		printf("%d ",x[c+(r!=0)]);
		if(r==0)
			printf("%d ",x[n]);
		else
			printf("%d ",x[r]);
	}
}
int main(){
	int i,j,k,ex,tr;
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);
	scanf("%d %d", &n, &S);
	for(i=1;i<=n;i++)
		scanf("%d",&x[i]);
	for(i=1;i<= n; i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
			v[++num]=x[i]+x[j]+x[k];
	for(i=1;i<=num;i++)
		p[i]=i;
	sort(1,num);
	tr=1;
	for(i=1;i<=num&&tr;++i){
		ex=caut(S-v[i]);
		if(ex){
			poz(p[i]);
			poz(p[ex]);
			tr = 0;
		}
	}
	if(tr)
		printf("-1\n");
	return 0;
}