Cod sursa(job #21386)

Utilizator amadaeusLucian Boca amadaeus Data 23 februarie 2007 14:07:03
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct cls {
	long suma;
	int i1, i2, i3;
	bool operator< ( const cls& x ) const {
		return suma < x.suma;
	}
};

vector< long > v;
int N;
long S;

void cit() {
	ifstream f( "loto.in" );
	int x;
	
	f >> N >> S;
	for( int i=0; i<N; i++ ) {
		f >> x;
		v.push_back( x );
	}
}

int bs( const vector<cls>& a, const long& val ) {
	int i, step, n = a.size();

	for( step=1; step<n; step <<= 1 );

	for( step>>=1, i=n-1; a[i].suma != val && step; step >>= 1 )
		if( a[ i - step ].suma >= val )
			i -= step;
	if( a[i].suma == val )
		return i;
	else
		return -1;
}

void rez() {
	cls x;
	vector< cls > a;
	int i, j, k, poz;
	
	for( i=0; i<N; i++ )
		for( j=i; j<N; j++ )
			for( k=j; k<N; k++ ) {
				x.suma = v[i] + v[j] + v[k];
				x.i1 = i; x.i2 = j; x.i3 = k;
				a.push_back( x );
			}
	sort( a.begin(), a.end() );

	ofstream g( "loto.out" );
	for( i=0; i<N; i++ )
		for( j=i; j<N; j++ )
			for( k=j; k<N; k++ ) {
				poz = bs( a, S - v[i] - v[j] - v[k] );
				if( poz != -1 ) {
					x = a[poz];
					g<<v[i]<<" "<<v[j]<<" "<<v[k]<<" "<<v[x.i1]<<" "<<v[x.i2]<<" "<<v[x.i3]<<endl;
					return;
				}
			}
	g<<"-1"<<endl;
}

int main() {
	cit();
	rez();
	return 0;
}