Cod sursa(job #1266662)

Utilizator dorinmoldovanMoldovan Dorin dorinmoldovan Data 18 noiembrie 2014 23:22:19
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include "stdio.h"
#include "stdlib.h"

#define MAX 100000001

FILE *f, *g;
int nr[101];
int S;
int N;

typedef struct number {
	int i;
	int j;
	int k;
	int sum;
};

number n[1000001];
int index, size;
int ok;

/* 
The function is used to merge two arrays:
arr[left..middle];
arr[middle+1..right];
of the array arr
*/
void merge(number* arr, int left, int middle, int right)
{
	int i, j, k;
	int n1 = middle - left + 1;
	int n2 = right - middle;

	/* create temporary arrays */
	number *L, *R;

	L = (number*)(malloc(n1 * sizeof(number)));
	R = (number*)(malloc(n2 * sizeof(number)));

	/* populate the two arrays L[] and R[] */

	for(i = 0; i < n1; i++)
		L[i] = arr[i+left];
	for(j = 0; j < n2; j++)
		R[j] = arr[j+1+middle];

	/* merge the temporary arrays back into arr[left..right] */

	i = 0;
	j = 0;
	k = left;

	while(i < n1 && j < n2)
	{
		if(L[i].sum < R[j].sum)
		{
			arr[k] = L[i];
			i++;
		}
		else
		{
			arr[k] = R[j];
			j++;
		}
		k++;
	}

	/* Copy the remaining elements of L[] */

	while(i < n1)
	{
		arr[k] = L[i];
		i++;
		k++;
	}

	/* Copy the remaining elements of R[] */

	while(j < n2)
	{
		arr[k] = R[j];
		j++;
		k++;
	}

	free(L);
	free(R);
}

void mergeSort(number* arr, int left, int right)
{
	if(left < right)
	{
		int middle = left + (right - left) / 2;
		mergeSort(arr, left, middle);
		mergeSort(arr, middle + 1, right);
		merge(arr, left, middle, right);
	}
}

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

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

	for(int i = 1; i <= N; i++)
		fscanf(f, "%d", &nr[i]);

	index = 1;

	for(int i = 1; i <= N; i++)
		for(int j = 1; j <= N; j++)
			for(int k = 1; k <= N; k++)
			{
				n[index].i = nr[i];
				n[index].j = nr[j];
				n[index].k = nr[k];
				n[index].sum = nr[i] + nr[j] + nr[k];
				index++;
			}

	size = index - 1;

	//mergeSort(n, 1, size);

	ok = 1;

	for(int i = 1; i <= size; i++)
	{
		int sum = S - n[i].sum;
		int a = 1;
		int b = size;

		for(;a<=b&&ok;)
		{
			int middle = (a+b) / 2;
			if(n[middle].sum == sum)
			{
				fprintf(g, "%d %d %d %d %d %d", n[i].i, n[i].j, n[i].k, n[middle].i, n[middle].j, n[middle].k);
				ok = 0;
			}
			if(n[middle].sum > sum)
				b = middle - 1;
			if(n[middle].sum < sum)
				a = middle + 1;
		}
	}

	if(ok)
		fprintf(g, "-1");

	fclose(f);
	fclose(g);
	return 0;
}