Cod sursa(job #669084)

Utilizator JBaccountCatalin JBaccount Data 26 ianuarie 2012 02:57:56
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

#define NM 105

int N, S, sir[NM*NM*NM], A[NM];

int main()
{
	freopen ("loto.in", "r", stdin);
	freopen ("loto.out", "w", stdout);
	
	scanf ("%d %d", &N, &S);
	
	for (int i = 1; i <= N; ++i) scanf ("%d", &A[i]);
	
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			for (int k = 1; k <= N; ++k)
				if (A[i] + A[j] + A[k] <= S) sir[++sir[0]] = A[i] + A[j] + A[k];
			
	sort (sir + 1, sir + sir[0] + 1);

	int found = 0, p1, p2;			
				
	for (int i = 1; i <= sir[0]; ++i)
	{
		int val = sir[i];
		int lf = S - val;
		
		int st = 1, dr = sir[0];
		
		if (lf < sir[st] || sir[dr] < lf) continue;
		
		while (st < dr)
		{
			int mij = (st + dr)/2;
			if (sir[mij] == lf)
			{
				st = dr = mij;
				break;
			}	
			if (sir[mij] < lf) st = mij + 1;
			else dr = mij - 1;
		}	
		
		if (sir[st] == lf)
		{
			found = 1;
			p1 = val;
			p2 = lf;
			break;
		}	
	}	
	
	if (!found) 
	{
		printf ("-1");
		return 0;
	}	
	else
	{
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= N; ++j)
				for (int k = 1; k <= N; ++k)
					if (A[i] + A[j] + A[k] == p1) 
					{
						printf ("%d %d %d ", A[i], A[j], A[k]);
						for (int i = 1; i <= N; ++i)
							for (int j = 1; j <= N; ++j)
								for (int k = 1; k <= N; ++k)
									if (A[i] + A[j] + A[k] == p2) 
									{
										printf ("%d %d %d ", A[i], A[j], A[k]);
										return 0;
									}
						return 0;			
					}	
	}	
	
	return 0;
}