Cod sursa(job #474048)

Utilizator andrey932Andrei andrey932 Data 2 august 2010 10:15:41
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

FILE *fin=fopen("loto.in","r"), *fout=fopen("loto.out","w");
struct elem{
	int val,poz;
};

bool compara(elem a, elem b) {
	return a.val<b.val;
}

int S,sm,n,i,j,k,nr[202],tsm,lo,hi,mi,rez[6];
elem sum[1000001];
bool ok;

int main() {
	fscanf(fin,"%i %i",&n,&S);
	for(i=0;i<n;i++) {
		fscanf(fin,"%i",&nr[i]);
	}
	tsm=-1;
	for(i=0;i<n;i++) {
		for(j=i;j<n;j++) {
			for(k=j;k<n;k++) {
				tsm++;
				sum[tsm].val=nr[i]+nr[j]+nr[k];	
				sum[tsm].poz=(i*n+j)*n+k;
			}
		}
	}

	sort(&sum[0],&sum[tsm+1],compara);	
	ok=false;
	for(i=0;i<=tsm;i++) {
		sm=S-sum[i].val;
		lo=0; hi=tsm;
		if (sm>0) {
		while(lo<hi) {
			mi=(lo+hi)>>1;
			if (sm<sum[mi].val) {
				hi=mi-1;
			}
			else if (sm>sum[mi].val) {
				lo=mi+1;
			}
			else break;			
		}	
		if (sum[i].val+sum[mi].val==S) {
			ok=true;
			int ii=sum[i].poz;
			mi=sum[mi].poz;
			rez[0]=nr[ii%n];
			rez[1]=nr[(ii/n)%n];
			rez[2]=nr[(ii/n/n)%n];
			rez[3]=nr[mi%n];
			rez[4]=nr[(mi/n)%n];
			rez[5]=nr[(mi/n/n)%n];
			sort(&rez[0],&rez[6]);
			fprintf(fout,"%i %i %i %i %i %i",rez[0],rez[1],rez[2],rez[3],rez[4],rez[5]);
			break;
		}
		}
	}
if (!ok) fprintf(fout,"%s","-1");
fprintf(fout,"%s","\n");
fclose(fout);
	return 0;
}