Cod sursa(job #855513)

Utilizator ioanapopaPopa Ioana ioanapopa Data 15 ianuarie 2013 00:59:23
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<cstdio>
#include<algorithm>

using namespace std;

#define nMax 101

int N, S, Cont;
int v[nMax];

struct Sums {
	int x, y, z;
	int s;
	} p[nMax*nMax*nMax];

int cmp (const void *x, const void *y)
{
	Sums a=*((Sums *)x);
	Sums b=*((Sums *)y);

	return a.s - b.s;
}

void partialSums()
{
	int k=0;
	for(int i=1; i<=N; i++)
		for(int j=1; j<=N; j++)
			for(int l=1; l<=N; l++)
				p[++k].s = v[i] + v[j] + v[l],
				p[k].x = v[i],
				p[k].y = v[j],
				p[k].z = v[l];
}

void inPut()
{
	freopen ( "loto.in", "r", stdin );
	scanf ( "%d %d", &N, &S );
	
	for(int i=1; i<=N; i++)
		scanf ( "%d", &v[i] );
	fclose(stdin);	
		
	sort ( v+1, v+N+1 );
}

void look(int st, int dr, int x)
{
	if ( st == dr )
	{
		if ( p[st].s == x )
			Cont = st;
		
		else
			Cont = 0;

		return;
	}

	int cen = (st+dr)/2;

	if ( x <= p[cen].s )
		look ( st, cen, x );
	
	else
		look ( cen+1, dr, x );
}

int main()
{
	inPut();
	partialSums();
	//qsort ( p+1, N*N*N, sizeof(Sums), cmp );

	int Kr=1;
	freopen ( "loto.out", "w", stdout );
	for(; p[Kr].s<S && Kr<=N; Kr++);

	for(int i=1; i<=N; i++)
		for(int j=1; j<=N; j++)
			for(int k=1; k<=N; k++)
			{
				look ( 1, Kr, S - v[i] - v[j] - v[k] );
				
				if ( Cont )
				{
					printf ( "%d %d %d %d %d %d\n", v[i], v[j], v[k], p[Cont].x, p[Cont].y, p[Cont].z );
					fclose(stdin);
					return 0;
				}
			}
	printf ( "-1\n" );
	fclose(stdin);
	
	return 0;
}