Cod sursa(job #715826)

Utilizator paulbotabota paul paulbota Data 17 martie 2012 19:57:08
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<fstream>
#define MAXN 102

using namespace std;

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

struct loto
{
	int suma,x,y,z;
};

loto s[MAXN*MAXN*MAXN];

int v[MAXN],sum,n,l,m;

void read()
{
	int i;
	in>>n>>sum;
	for(i=1;i<=n;i++)
		in>>v[i];
}

void sume()
{
	int i,j,k;
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)
			{
				s[++l].suma=v[i]+v[j]+v[k];
				s[l].x=v[i];
				s[l].y=v[j];
				s[l].z=v[k];
			}
}

void swap(int x,int y)
{
	loto aux=s[x];
	s[x]=s[y];
	s[y]=aux;
}

void heapify(int i)
{
	int stg,dr,max=i;
	stg=2*i;
	dr=2*i+1;
	if(stg<m && s[stg].suma>s[i].suma)
		max=stg;
	if(dr<m && s[dr].suma>s[max].suma)
		max=dr;
	if(max!=i)
	{
		swap(max,i);
		heapify(max);
	}
}

void sortare()
{
	int i;
	for(i=m/2;i>=1;i--)
		heapify(i);
	for(i=2;i<=m;i++)
	{
		swap(1,m);
		m--;
		heapify(1);
	}
}

void rezolvare()
{
	int stg,dr;
	for(int i=1;i<=l;i++)
	{
	stg=1;
	dr=l;
	while(stg<=dr)
	{
		int mij=(stg+dr)/2,sumisoara=s[i].suma+s[mij].suma;
		if(sumisoara==sum)
		{
			out<<s[i].x<<" "<<s[i].y<<" "<<s[i].z<<" "<<s[mij].x<<" "<<s[mij].y<<" "<<s[mij].z<<"\n";
			return;
		}
		if(sumisoara>sum)
			stg++;
			else
				dr--;
	}
	}
	out<<"-1\n";
}

int main()
{
	read();
	sume();
	m=l;
	sortare();
	rezolvare();
	return 0;
}