Cod sursa(job #2354821)

Utilizator skoda888Alexandru Robert skoda888 Data 25 februarie 2019 16:51:38
Problema Loto Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb



#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>


const int NMAX = 103;


struct SumeDe3 {

	int suma;
	int a;
	int b;
	int c;

};

int NumereLoto[NMAX];
std::vector<SumeDe3> SumeDeTrei;

bool CompareSort(SumeDe3 A, SumeDe3 B) {
	return A.suma < B.suma;
}


int CautareBinara(int suma, int stanga, int dreapta) {

	if (stanga > dreapta) {
		return -1;
	}


	int mijloc = (stanga + dreapta) / 2;
	if (suma == SumeDeTrei[mijloc].suma) {
		return mijloc;
	}


	if (suma < SumeDeTrei[mijloc].suma) {
		return CautareBinara(suma, stanga, mijloc - 1);
	}
	else {
		return CautareBinara(suma, mijloc + 1, dreapta);
	}
}



int main() {

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


	int N, S;
	in >> N >> S;

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

	//{NumereLoto[i] + NumereLoto[j] + NumereLoto[k], NumereLoto[i], NumereLoto[j], NumereLoto[k]}
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			for (int k = 1; k <= N; ++k) {
				int suma = NumereLoto[i] + NumereLoto[j] + NumereLoto[k];
				SumeDeTrei.push_back({ suma, NumereLoto[i], NumereLoto[j], NumereLoto[k] });
			}
		}
	}

	std::sort(SumeDeTrei.begin(), SumeDeTrei.end(), CompareSort);

	int prev = -1;
	for (int i = 0; i < SumeDeTrei.size(); ++i) {
		int found = CautareBinara(S - SumeDeTrei[i].suma, 0, SumeDeTrei.size() - 1);
		if (prev != SumeDeTrei[i].suma && found > -1) {
			out << SumeDeTrei[i].a << ' ' << SumeDeTrei[i].b << ' ' << SumeDeTrei[i].c << ' ' << SumeDeTrei[found].a << ' ' << SumeDeTrei[found].b << ' ' << SumeDeTrei[found].c;
			return 0;
		}
	}
	
	out << -1;
	system("PAUSE");
	return 0;
}