Cod sursa(job #629368)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 3 noiembrie 2011 10:46:49
Problema Loto Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define MOD 666013
#define NMAX 100
#define PIIII pair< pair< int, int >, pair< int, int > >
#define nr1 first.first
#define nr2 first.second
#define nr3 second.first
#define suma second.second
#define pb push_back
#define mp make_pair

using namespace std;

int N, S, i, j, k, Nr[NMAX], r1, r2, r3;
vector< PIIII > H[MOD];

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

inline void Add( int x, int y, int z )
{
	int pos = ( x + y + z )%MOD;
	
	for( vector< PIIII >::iterator it = H[ pos ].begin(); it != H[ pos ].end(); ++it )
		if( x + y + z == (*it).suma ) return;
	
	H[ pos ].pb( mp( mp( x, y ), mp( z, x + y + z ) ) );
}

inline bool Find( int &a, int &b, int &c, int Suma )
{
	int pos = Suma%MOD;
	
	for( vector< PIIII >::iterator it = H[ pos ].begin(); it != H[ pos ].end(); ++it )
		if( Suma == (*it).suma )
		{
			a = (*it).nr1;
			b = (*it).nr2;
			c = (*it).nr3;
			return true;
		}
	
	return false;
}

int main()
{
	in >> N >> S;
	for( i = 0; i < N; ++i )
		in >> Nr[i];
	
	for( i = 0; i < N; ++i )
		for( j = 0; j < N; ++j )
			for( k = 0; k < N; ++k )
				Add( Nr[i], Nr[j], Nr[k] );
	
	for( i = 0; i < 666013; ++i )
		for( vector< PIIII >::iterator it1 = H[ i ].begin(); it1 != H[ i ].end(); ++it1 )
			if( Find( r1, r2, r3, S - (*it1).suma ) )
			{
				out << r1 << ' ' << r2 << ' ' << r3 << ' ' << (*it1).nr1 << ' ' << (*it1).nr2 << ' ' << (*it1).nr3 << '\n';
				return 0;
			}
	
	out << "-1\n";
	return 0;
}