Cod sursa(job #1455736)

Utilizator Salomia_Adrian_325CCSalomia Adrian Salomia_Adrian_325CC Data 28 iunie 2015 23:31:23
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct triplet {
	int i, j, k;
} triplet;

int partition(long *sume3, triplet *t, int l, int r) {
	int pivot = l;
	int lWall = l;
	int i;
	long aux1;
	triplet aux2;
	for(i = l+1;i <= r;i++)
		if (sume3[i] < sume3[pivot]){
			lWall = lWall + 1;
			aux1 = sume3[i];
			sume3[i] = sume3[lWall];
			sume3[lWall] = aux1;
			aux2 = t[i];
			t[i] = t[lWall];
			t[lWall] = aux2;
		}
	aux1 = sume3[l];
	sume3[l] = sume3[lWall];
	sume3[lWall] = aux1;
	aux2 = t[l];
	t[l] = t[lWall];
	t[lWall] = aux2;
	return lWall;	
}

void sortare(long *sume3, triplet *t, int l, int r) {
	int pivot;
	if(l < r) {
		pivot = partition(sume3, t, l, r);
		sortare(sume3, t, l, pivot - 1);
		sortare(sume3, t, pivot + 1, r);
	}
}

int cautare (long *v, long x, int l, int r) {
	if(l > r)
		return -1;
	int m = (l+r)/2;
	if(v[m] == x)
		return m;
	if(v[m] > x)
		return cautare(v, x, l, m-1);
	cautare(v, x, m+1, r);
}

int main() {
	FILE *f1 = fopen("loto.in", "r");
	FILE *f2 = fopen("loto.out", "w");

	int n;
	long S;
	fscanf(f1, "%d%ld", &n, &S);

	long *v = (long *) malloc (n * sizeof(long));
	int i, j, k;
	for(i = 0;i < n;i++)
		fscanf(f1, "%ld", &v[i]);

	long *sume3 = (long *) malloc (pow(n, 3)*sizeof(long));
	int z = 0;
	triplet *t = (triplet *) malloc (pow(n, 3)*sizeof(triplet));

	for(i = 0;i < n;i++)
		for(j = 0;j < n;j++)
			for(k = 0;k < n;k++) {
				t[z].i = i;
				t[z].j = j;
				t[z].k = k;
				sume3[z++] = v[i] + v[j] + v[k];
			}

	sortare(sume3, t, 0, pow(n, 3)-1);
	int g = 0;
	k = pow(n, 3);
	for(i = 0;i < k;i++) {
		if(cautare(sume3, S-sume3[i], i, k-1) != -1) {
			z = cautare(sume3, S-sume3[i], i, k-1);
			break;
		}
	}

	if(i == pow(n, 3) || g == 1) {
		fprintf(f2, "-1\n");
	}
	else {
		fprintf(f2, "%ld %ld %ld %ld %ld %ld\n", v[t[i].i], v[t[i].j], v[t[i].k], v[t[z].i], v[t[z].j], v[t[z].k]);
	}

	fclose(f1);
	fclose(f2);
	return 0;
}