Cod sursa(job #2434134)

Utilizator stratonedanielDaniel Stratone stratonedaniel Data 30 iunie 2019 17:58:23
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define null NULL
#define in "loto.in"
#define out "loto.out"

class Sum{
	public:
		Sum(int sum, int firstNumber, int secondNumber, int thirdNumber)
		{
			this -> sum = sum;
			this -> firstNumber = firstNumber;
			this -> secondNumber = secondNumber;
			this -> thirdNumber = thirdNumber;
		}

	int sum;
	int firstNumber;
	int secondNumber;
	int thirdNumber;

};

using namespace std;

vector<Sum> sume;
int array[100000];

bool compare(Sum a, Sum b)
{
	return b.sum > a.sum;
}

int binarySearch(int left, int right, int to_be_found)
{
	if (left <= right)
	{
		int middle = left + (right - left)/2;

		if (sume[middle].sum == to_be_found)
			return middle;

		if (sume[middle].sum > to_be_found)
			return binarySearch(left, middle , to_be_found);
		else
			return binarySearch(middle + 1, right, to_be_found);

	}

	return -1; 
}



int main(int argc, char const *argv[])
{
	ifstream read(in);
	ofstream write(out);

	int N, S;

	read >> N >> S;

	for (int i = 0; i < N; i++)
		read >> array[i];

	for (int i = 0; i < N; i++)
		for (int j = i; j < N; j++)
			for (int k = j; k < N; k++)
			{
				Sum suma_noua(array[i] + array[j] + array[k], array[i], array[j], array[k]);
				sume.push_back(suma_noua);
			}

	sort(sume.begin(), sume.end(), compare);

	int status = -1;

	for (int i = 0; i < sume.size(); i++)
	{
		status = binarySearch(0, sume.size(), S -  sume[i].sum);

		if (status != -1)
		{
			write << sume[i].firstNumber << " " << sume[i].secondNumber << " " << sume[i].thirdNumber
			<< " " << sume[status].firstNumber << " " << sume[status].secondNumber << " " << sume[status].thirdNumber << '\n';
		
			return 0;
		}
	}

	write << "-1" << '\n';

	read.close();
	write.close();

	return 0;
}