Cod sursa(job #178224)

Utilizator c_sebiSebastian Crisan c_sebi Data 14 aprilie 2008 11:36:46
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream.h>
#define Ma 101

int s[Ma*Ma*Ma], v[Ma], S, n, ns;
ofstream g("loto.out");

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

int gasit(int S){
	int st=0, dr=ns-1, m;
	while(st<=dr){
		m=(st+dr)/2;
		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(){
	ifstream f("loto.in");
	int i, j, k;
	f>>n>>S;
	for(i=0; i<n; i++)
		f>>v[i];
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
			for(k=0; k<n; k++)
				s[ns++] = v[i]+v[j]+v[k];
	quick(s, 0, ns-1);
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
			for(k=0; k<n; k++)
				if(gasit(S-v[i]-v[j]-v[k])){
					g<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
					scrie(S-v[i]-v[j]-v[k]);
					return 0;
				}
	g<<"-1\n";
	return 0;
}