Cod sursa(job #715929)

Utilizator paulbotabota paul paulbota Data 17 martie 2012 22:47:12
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define MAXN 102
#define pb push_back

using namespace std;

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

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

bool cmp(loto param,loto param1)
{
	return param.suma>param1.suma;
}


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 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=mij+1;
		else
			dr=mij-1;
	}
	}
	out<<"-1\n";
}

int main()
{
	read();
	sume();
	sort(s,s+l,cmp);
	rezolvare();
	return 0;
}