Cod sursa(job #1455743)

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

int partition(long *sume3, int l, int r) {
	int pivot = l;
	int lWall = l;
	int i;
	long aux1;
	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;
		}
	aux1 = sume3[l];
	sume3[l] = sume3[lWall];
	sume3[lWall] = aux1;
	return lWall;	
}

void sortare(long *sume3, int l, int r) {
	int pivot;
	if(l < r) {
		pivot = partition(sume3, l, r);
		sortare(sume3, l, pivot - 1);
		sortare(sume3, 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;

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

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

	if(i == pow(n, 3) || g == 1) {
		fprintf(f2, "-1\n");
	}
	else {
		long i1, i2, j1, j2, k1, k2, s1, s2, s;
		int adi1 = 0, adi2 = 0;
		s1 = sume3[i];
		s2 = sume3[z];
		for(i = 0;i < n;i++)
			for(j = 0;j < n;j++)
				for(k = 0;k < n;k++) {
					s = v[i] + v[j] + v[k];
					if(s == s1 && adi1 == 0) {
						adi1 = 1;
						i1 = v[i];
						j1 = v[j];
						k1 = v[k];
						if(adi2) {
							i = n;
							j = n;
							k = n;
						}
					}
					if(s == s2 && adi2 == 0) {
						adi2 = 1;
						i2 = v[i];
						j2 = v[j];
						k2 = v[k];
						if(adi1) {
							i = n;
							j = n;
							k = n;
						}
					}
				}
		fprintf(f2, "%ld %ld %ld %ld %ld %ld\n", i1, j1, k1, i2, j2, k2);
	}

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