Cod sursa(job #2976733)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 9 februarie 2023 22:07:05
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>

#define NMAX 1003


using namespace std;


FILE* fin, * fout;

int n, num = 0;
long long int target;
int v[NMAX];
struct elem {
	int a, b, c;
	long long int sum;
}sume[NMAX*NMAX];

bool cmp(elem x, elem y)
{
	return x.sum > y.sum;
}

int main()
{
	fin = fopen("loto.in", "r");
	fout = fopen("loto.out", "w");

	fscanf(fin, "%d %d", &n,&target);
	for (int i = 1; i <= n; i++)
	{
		fscanf(fin, "%d", &v[i]);
	}
	
	//fac sumele de cate 3
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			for (int k = 1; k <= n; k++)
			{
				sume[++num] = { v[i],v[j],v[k],v[i] + v[j] + v[k] };
			}
		}
	}
	sort(sume + 1, sume + num + 1, cmp);

	for (int i = 1; i <= num; i++)
	{
		int s = target - sume[i].sum;
		int st = i + 1;
		int dr = num;
		while (st <= dr)
		{
			int mij = (st + dr) / 2;
			if (sume[mij].sum == s)
			{
				//am gasit solutie
				fprintf(fout, "%d %d %d %d %d %d\n", sume[i].a, sume[i].b, sume[i].c, sume[mij].a, sume[mij].b, sume[mij].c);
				return 0;
			}
			else if (sume[mij].sum < s)
			{
				st = mij + 1;
			}
			else {
				dr = mij - 1;
			}
		}
	}
	fprintf(fout, "-1");
	return 0;
}