Cod sursa(job #1077635)

Utilizator stanescu.raduRadu Stanescu stanescu.radu Data 11 ianuarie 2014 15:37:38
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

struct suma
{
	int s;
	int a,b,c;
};
int v[105],i,j,s,n,k,x,nr,st,dr,m;
suma t[1000005];

int cmp (suma x, suma y)
{
	if (x.s < y.s)
		return x.s;
	else 
		return y.s;
}

int main ()
{
	f >> n >> s;
	for (i = 1; i <= n; i++)
		f >> v[i];
	for (i = 1; i <= n; i++)
		for (j = i; j<= n; j++)
			for (k = j; k <= n; k++)
			{
				t[++nr].s = v[i] + v[j] + v[k];
				t[nr].a = v[i];
				t[nr].b = v[j];
				t[nr].c = v[k];
			}
	sort (t + 1, t + nr + 1, cmp);
	k = 0;
	for (i = 1; i <= nr && k == 0; i++)
	{
		if (t[i].s < s)
		{
			st = i; 
			dr = nr;
            while(st <= dr)
			{
                m = st + (dr - st) / 2;
                if(t[m].s == s - t[i].s)
				{
                    g << t[m].a << " " << t[m].b << " " << t[m].c << " " << t[i].a << " " << t[i].b << " " << t[i].c;
                    k = 1;
					break;
				}
				else
				{
                    if(t[m].s > s - t[i].s)
                        dr = m -1;
                    else
                        st = m + 1;
				}
			}
		}
	}
	if (k == 0) g << '-1';
	f.close();
	g.close();
	return 0;
}