Cod sursa(job #444894)

Utilizator siminescuPaval Cristi Onisim siminescu Data 21 aprilie 2010 23:54:55
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<stdio.h>
int a[101],n,s,v[1000001],aux,pozi[3][1000001],poz=-1;
void citire()
{
	freopen("loto.in","r",stdin);
	scanf("%d%d",&n,&s);
	int i;
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
}
void swap(int x,int y)
{
	aux=v[x];v[x]=v[y];v[y]=aux;
	aux=pozi[1][x];pozi[1][x]=pozi[1][y];pozi[1][y]=aux;
	aux=pozi[0][x];pozi[0][x]=pozi[0][y];pozi[0][y]=aux;
	aux=pozi[2][x];pozi[2][x]=pozi[2][y];pozi[2][y]=aux;
}
void downHeap(int from,int to)
{
	for(int son=2*from;son<to;from=son,son=2*from)
	{
		if(son<to-1&&v[son+1]>v[son])
			son++;
		if(v[from]>=v[son])
			return;
		swap(son,from);
	}
}
void HeapSort(int from,int to)
{
	int i=(to-from)/2;
	for(;i>=0;i--)
		downHeap(i,to);
	while(to>from)
	{
		swap(from,to-1);
		to--;
		downHeap(from,to);
	}
}
void init_a()
{
	int i,j,k;
	for(i=0;i<n;i++)
		for(j=i;j<n;j++)
			for(k=j;k<n;k++)
			{
				poz++;v[poz]=a[i]+a[j]+a[k];
				pozi[0][poz]=i;pozi[1][poz]=j;pozi[2][poz]=k;
			}
}
int main()
{
	citire();
	init_a();
	HeapSort(0,poz+1);
	int i,m,dr,st,ss;
	freopen("loto.out","w",stdout);
	for(i=0;i<=poz;i++)
	{
		if(v[i]>=s)
			break;
		ss=s-v[i];
		dr=poz;st=0;
		while(st<dr)
		{
			m=(dr+st)/2;
			if(v[m]==ss)
			{
				printf("%d %d %d %d %d %d\n",a[pozi[0][i]],a[pozi[1][i]],a[pozi[2][i]],a[pozi[0][m]],a[pozi[1][m]],a[pozi[2][m]]);
				return 0;
			}
			if(v[m]>ss)
				dr=m;
			else;
			st=m+1;
		}
	}
	printf("-1\n");
}