Cod sursa(job #579434)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 12 aprilie 2011 09:45:38
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <cstdio>

using namespace std;

int s, n, a[102];
struct Sume
{
	int s, x1, x2, x3;
};
Sume v[1000005];

inline bool cmp (const Sume A, const Sume B)
{
	return A.s<B.s;
}

int main ()
{
	freopen ("loto.in", "r", stdin);
	scanf ("%d %d\n", &n, &s);
	int i, contor=0;
	for (i=0; i<n; i++)
		scanf ("%d ", &a[i]);
	int j, k;
	for (i=0; i<n; i++)
		for (j=i; j<n; j++)
			for (k=j; k<n; k++)
			{
				v[contor].s=a[i]+a[j]+a[k];
				v[contor].x1=a[i];
				v[contor].x2=a[j];
				v[contor].x3=a[k];
				contor++;				
			}
	sort (v, v+contor, cmp);
	freopen ("loto.out", "w", stdout);
	int st, dr, m, suma;
	
	for (i=0; i<contor; i++)
	{
		st=0;
		dr=contor-1;
		suma=s-v[i].s;
		while (st<=dr)
		{
			m=(st+dr)/2;
			if (v[m].s==suma)
			{
				printf ("%d %d %d %d %d %d\n", v[i].x1, v[i].x2, v[i].x3, v[m].x1, v[m].x2, v[m].x3);
				return 0;
			}
			else
				if (v[m].s<s)
					dr=m-1;
				else
					st=m+1;
		}
	}
	printf ("-1\n");	
	return 0;
}