Cod sursa(job #1455902)

Utilizator Salomia_Adrian_325CCSalomia Adrian Salomia_Adrian_325CC Data 29 iunie 2015 13:28:22
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;

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

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 = i;j < n;j++)
			for(k = j;k < n;k++) {
				sume3[z++] = v[i] + v[j] + v[k];
			}

	k = z-1;
	sort(sume3, sume3 + k + 1);

	int s;
	z = -1;
	for(i = 0;i <= k;i++) {
		s = S-sume3[i];
		if(sume3[k] < s)
			continue;
		if(sume3[i] > s) {
			break;
		}
		z = cautare(sume3, s, i, k);
		if(z != -1)
			break;
	}
	if(z == -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 = i;j < n;j++)
				for(k = j;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;
}