Cod sursa(job #428430)

Utilizator ErgoVicol Sergiu Constantin Ergo Data 29 martie 2010 11:38:50
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <vector>

#define SMAX 1000010
#define NMAX 127
using namespace std;

vector<int> A;
int  N, NR[NMAX], S;

int main()
{
	ifstream fin("loto.in");
	ofstream fout("loto.out");
	
	int i, j, k, st, end, m;
	
	fin >>N >>S;
	
	for (i = 1; i <= N; i++)
		fin >>NR[i];
	
	for (i = 1; i <= N; i++)
		for (j = 1; j<= N; j++)
			for (k = 1; k <= N; k++)
				A.push_back( NR[i] + NR[j] + NR[k]);
			
	for (i = 0; i < A.size(); i++)
	{
		st = 0, end = A.size(), m;
		while (st <= end)
		{
			m = (st + end) / 2;
			
			if (A[m] > S - A[i]) end = m - 1;
			if (A[m] < S - A[i]) st = m + 1;
			
			if (A[m] == S - A[i])
			{
				for (i = 1; i <= N; i++)
					for (j = 1; j<= N; j++)
						for (k = 1; k <= N; k++)
							if( NR[i] + NR[j] + NR[k] == A[m] ) 
								fout << NR[i] <<' ' <<NR[j] <<' ' <<NR[k] <<' ', i = j = k = N + 1;
							
				for (i = 1; i <= N; i++)
					for (j = 1; j<= N; j++)
						for (k = 1; k <= N; k++)
							if( NR[i] + NR[j] + NR[k] == S - A[m] ) 
								fout << NR[i] <<' ' <<NR[j] <<' ' <<NR[k] <<' ', i = j = k = N + 1;
							
				fout.close();
				return 0;
			}
		}
	}
	fout <<"-1";
	fout.close();
	return 0;
}