Cod sursa(job #447166)

Utilizator voikybodea voichita voiky Data 27 aprilie 2010 21:19:27
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
using namespace std;

int n,s,x[101],suma[1000001],p=0,indice[3][1000001];

void schimb(int &x,int &y)
{
	int aux=x;x=y;y=aux;
}

void ordon()
{
	int i,j;
	for(i=1;i<p;i++)
		for(j=i+1;j<=p;j++)
			if(suma[i]>suma[j])
			{
				schimb(suma[i],suma[j]);
				schimb(indice[0][i],indice[0][j]);
				schimb(indice[1][i],indice[1][j]);
				schimb(indice[2][i],indice[2][j]);
			}
}

int caut(int st,int dr,int valoare,int &indice)
{
	indice=0;
	while(st<=dr && indice==0)
	{
		int m=st+(dr-st)/2;
		if(valoare==suma[m])indice=m;
		else if(valoare>suma[m])st=m+1;
			 else dr=m-1;
	}
	return indice;
}

int main()
{
	ifstream f("loto.in");ofstream g("loto.out");
	int i,j,k;
	f>>n>>s;for(i=1;i<=n;i++)f>>x[i];
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)
			{
				suma[++p]=x[i]+x[j]+x[k];				
				indice[0][p]=i;indice[1][p]=j;indice[2][p]=k;
			}	
	ordon();
	for(i=1;i<=p;i++)
		if(caut(1,p,s-suma[i],j))
		{
			g<<x[indice[0][i]]<<' '<<x[indice[1][i]]<<' '<<x[indice[2][i]]<<' '<<x[indice[0][j]]<<' '<<x[indice[1][j]]<<' '<<x[indice[2][j]];
			f.close();g.close();
			return 0;
		}	
	g<<-1;
	f.close();g.close();
	return 0;
}