Cod sursa(job #178249)

Utilizator c_sebiSebastian Crisan c_sebi Data 14 aprilie 2008 12:09:18
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#include <algorithm>
#define Ma 101
using namespace std;

int s[Ma*Ma*Ma], v[Ma], S, n, ns;
FILE *g=fopen("loto.out", "w");

void scrie(int S){
	int i, j, k;
	for(i=0; i<n; i++)
		for(j=i; j<n; j++)
			for(k=j; k<n; k++)
				if(v[i]+v[j]+v[k]==S){
					fprintf(g, "%d %d %d ", v[i], v[j], v[k]);
					return ;
				}
}

int gasit(int S){
	int st=0, dr=ns-1, m;
	while(st<=dr){
		m=(st+dr)>>1;
		if(s[m] > S) dr = m-1;
		else if(s[m] < S) st=m+1;
		else return m+1;
	}
	return 0;
}

void quick(int x[], int st, int dr){
	int i=st, j=dr, ii=0, jj=-1, aux;
	if(st < dr){
		while(i<j){
			if(x[i] > x[j]){
				aux=x[i]; x[i]=x[j]; x[j]=aux;
				aux=-ii; ii=-jj; jj=aux;
			}
			i+=ii;
			j+=jj;
		}
		quick(x, st, i-1);
		quick(x, i+1, dr);
	}
}




int main(){
	FILE *f=fopen("loto.in", "r");

	int i, j, k;
	fscanf(f, "%d %d", &n, &S);
	for(i=0; i<n; i++)
		fscanf(f, "%d", &v[i]);
	for(i=0; i<n; i++)
		for(j=i; j<n; j++)
			for(k=j; k<n; k++)
				s[ns++] = v[i]+v[j]+v[k];
	//quick(s, 0, ns-1);
	sort(s, s+ns);
	for(i=0; i<ns; i++)
				if(gasit(S-s[i])){
					scrie(s[i]);
					scrie(S-s[i]);
					return 0;
				}
	fprintf(g, "-1\n");
	return 0;
}