Cod sursa(job #782909)

Utilizator AndreeaNNedelcu Andreea AndreeaN Data 30 august 2012 16:40:54
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f=fopen("loto.in","r"),*g=fopen("loto.out","w");
long int n,s,sume[1000009],v[103],k=0;

void citire(){
long int i;
	fscanf(f,"%ld %ld\n",&n,&s);
	for(i=1; i<=n; i++){
		fscanf(f,"%ld ",&v[i]);
	}
}

void sume_partiale(){
long int i,j,t;
	for(i=1; i<=n; i++){
		for(j=i; j<=n; j++){
			for(t=j; t<=n; t++){
				k++;
				sume[k]=v[i]+v[j]+v[t];
			}
		}
	}
	sort(sume+1, sume+k+1);
}

long diferenta(long int sum){
long int st=0,dr=k,mij=0;
	while(st<=dr){
		mij=(st+dr)/2;
		if(sume[mij]==sum){return 1;}
		if(sume[mij]<sum){
			st=mij+1;
		}
		else{
			dr=mij-1;
		}
	}
	return 0;
}

void reconstituire(long int sum){
long int i,j,t;
	for(i=1; i<=n; i++){
		for(j=i; j<=n; j++){
			for(t=j; t<=n; t++){
				if(sum==v[i]+v[j]+v[t]){
					fprintf(g,"%ld %ld %ld",v[i],v[j],v[t]);
					return;
				}
			}
		}
	}
	return ;
}

void parcurgere(){
long int i,ok=0;
	for(i=1; i<=k; i++){
		if(diferenta(s-sume[i])==1){
			reconstituire(sume[i]);
			fprintf(g," ");
			reconstituire(s-sume[i]);
			ok=1;
			break;
		}
	}
	if(ok==0){fprintf(g,"-1");}
}


int main(){
	citire();
	sume_partiale();
	parcurgere();
return 0;
}