Cod sursa(job #2434042)

Utilizator stratonedanielDaniel Stratone stratonedaniel Data 30 iunie 2019 14:41:59
Problema Loto Scor 5
Compilator c-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

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

typedef struct partial
{
	int sum;
	int firstNumber;
	int secondNumber;
	int thirdNumber;
}Sums;

int array[1000000];
Sums set[10000000];

void addPartialSum(int *size, int sum, int firstNumber, int secondNumber, int thirdNumber)
{
	(*size) ++;

	set[(*size) - 1].sum = sum;
	set[(*size) - 1].firstNumber = firstNumber;
	set[(*size) - 1].secondNumber = secondNumber;
	set[(*size) - 1].thirdNumber = thirdNumber;
}

int compare(const void *a, const void *b)
{
	return (*((int *)a)) - (*((int *)b));
}

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

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

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

}


int main(int argc, char const *argv[])
{
	FILE *read = (FILE *) fopen(in, "r");
	FILE *write = (FILE *) fopen(out, "w");
	
	int size = 0;

	int N, S;

	fscanf(read, "%d%d", &N, &S);

	for (int i = 0; i < N; i++)
		fscanf(read, "%d", &array[i]);

	qsort(array, N, sizeof(int), compare);

	for (int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			for(int k = 0; k < N; k++)
			{
				int partial_sum = array[i] + array[j] + array[k];

				if (partial_sum < S)
					addPartialSum(&size, partial_sum, array[i], array[j], array[k]);	
			}

	int answer[6], status = -1;

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

		if (status != -1)
		{
			answer[0] = set[i].firstNumber;
			answer[1] = set[status].firstNumber;
			answer[2] = set[i].secondNumber;
			answer[3] = set[status].secondNumber;
			answer[4] = set[i].thirdNumber;
			answer[5] = set[status].firstNumber; 

			qsort(answer, 6, sizeof(int), compare);

			for(int j = 0; j < 6; j++)
			{
				if (j != 5)
					fprintf(write, "%d ", answer[j]);
				else
					fprintf(write, "%d\n", answer[j]);
			}	

			break;
		}
	}

	if (status == -1)
		fprintf(write, "-1\n");


	fclose(read);
	fclose(write);
	
	return 0;
}