Cod sursa(job #2434110)

Utilizator stratonedanielDaniel Stratone stratonedaniel Data 30 iunie 2019 16:30:16
Problema Loto Scor 5
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.9 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];

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 = i; j < N; j++)
			for(int k = j; k < N; k++)
			{
				int partial_sum = array[i] + array[j] + array[k];

				if (partial_sum < S)
				{
					size++;

					set[size - 1].sum = partial_sum;
					set[size - 1].firstNumber = array[i];
					set[size - 1].secondNumber = array[j];
					set[size - 1].thirdNumber = array[k];
				}	
			}


	int answer[6], status = -1;


	for (int i = 0; i < size; i++)
	{
		status = binarySearch(set, 0, size - 1, 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; 

			fprintf(write, "%d %d %d %d %d %d\n", answer[0], answer[1], answer[2], answer[3], answer[4], answer[5]);
			
			return 0;
		}
	}

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