Cod sursa(job #721871)

Utilizator runnerbloodVoda Alexandru-Ioan runnerblood Data 24 martie 2012 12:33:17
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <algorithm>
using namespace std;

int N, S, v[101], sum[1000000], nr;

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

void construiescSum(){
	for(int i=1 ; i<=N ; i++)
		for(int j=i ; j<=N ; j++)
			for(int k=j ; k<=N ; k++)
				sum[++nr] = v[i] + v[j] + v[k];
	sort(&sum[1],&sum[nr+1]);
}

int caut(int val) {
	int i, pas=1<<28;
    for (i=0; pas!=0; pas >>= 1)
        if (i + pas < N && sum[i + pas] <= val)
           i += pas;
    if(sum[i] == val) return i;
	return -1;
}

void citesc() {
	for (int i=1; i<=N; i++) {
		in >> v[i];
	}
}


void scrie(int s) {
	for(int i=1; i<=N; i++)
		for(int j=i; j<=N; j++)
			for(int k=j; k<=N; k++)
				if(v[i] + v[j] + v[k] == s)
				{
					out << v[i] << " " << v[j] << " " << v[k] << "\n";
					return;
				}
}
	
void rezolva()
{
	for(int i=1; i<=N; i++) {
		for(int j=i; j<=N; j++) {
			for(int k=j; k<=N; k++)
			{
				int r = caut(S - (v[i]+v[j]+v[k]));
				if(r == -1) continue;
				out << v[i] << " " << v[j] << " " << v[k] << " ";
				scrie(S - (v[i]+v[j]+v[k]));
				return;
			}
		}
	}
	out << "-1\n";
}


int main() {
	in >> N >> S;
	citesc();
	construiescSum();
	rezolva();
	return 0;
}