Cod sursa(job #476817)

Utilizator mottyMatei-Dan Epure motty Data 12 august 2010 13:30:12
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=101, M=1000001;

int n, s, ind, v[N], sum[M];

void Read()
{
	scanf( "%d%d", &n, &s);
	
	for( int i=1; i<=n; ++i)
		scanf( "%d", &v[i]);
}

void GetSum()
{
	for( int i=1; i<=n; ++i)
		for( int j=i; j<=n; ++j)
			for( int k=j; k<=n; ++k)
				sum[++ind]=v[i]+v[j]+v[k];
	
	sort( sum+1, sum+ind+1);
}

bool Find(int nr)
{
	int i,step;
	for( step=1; step<=ind; step<<=1);
	for( i=0; step; step>>=1)
		if(i+step<=ind && sum[i+step]<=nr)
			i+=step;
	if(sum[i]==nr)
		return 1;
	return 0;
}

void GetRest(int nr)
{
	for( int i=n; i; --i)
		for( int j=i; j; --j)
			for( int k=j; k; --k)
				if(v[i]+v[j]+v[k]==nr)
				{
					printf( "%d %d %d", v[k], v[j], v[i]);
					exit(0);
				}
}

void GetGood()
{
	for( int i=1; i<=n; ++i)
		for( int j=i; j<=n; ++j)
			for( int k=j; k<=n; ++k)
				if( Find(s-(v[i]+v[j]+v[k]))==1 )
				{
					printf( "%d %d %d ", v[i], v[j], v[k]);
					GetRest(s-(v[i]+v[j]+v[k]));
				}
	printf("-1\n");
}

int main()
{
	freopen( "loto.in", "r", stdin);
	freopen( "loto.out", "w", stdout);
	
	Read();
	GetSum();
	GetGood();
	
	return 0;
}