Cod sursa(job #468647)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 4 iulie 2010 15:00:53
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long a[100],s1,s[60000],i,j,k,t,s2,s3;
int n,ok;

int comp(const void *a,const void *b) {
	long *x=(long*)a;
	long *y=(long*)b;
	if (*x<*y) return -1;
	else if (*x==*y) return 0;
	else return 1;
}

int cautare(long x) {
	long poz,st,dr,m;
	poz=-1;
	st=0; dr=t;
	while (st<=dr && poz==-1) {
		m=(st+dr)/2;
		if (s[m]==x) poz=m;
		else {
			if (s[m]>x) dr=m-1;
		    else st=m+1;
		}
	}
	if (poz==-1) return 0;
	else return 1;
}
		

void afis () {
	int ok2,ok3;
	ok2=0; ok3=0;
	for (i=0; i<n; i++) 
		for (j=i; j<n; j++)
			for (k=j; k<n; k++) {
				if (ok2==0 || ok3==0) {
				if (a[i]+a[j]+a[k]==s2) {
					printf("%ld %ld %ld",a[i],a[j],a[k]);
					if (ok3==0) printf(" ");
					else printf("\n");
					ok2=1;
				}
				if (a[i]+a[j]+a[k]==s3) {
					printf("%ld %ld %ld",a[i],a[j],a[k]);
					if (ok2==0) printf(" ");
					else printf("\n");
					ok3=1;
				}
				}
				else break;
			}
}

int main () {
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d%ld\n",&n,&s1);
	for (i=0; i<n; i++) scanf("%ld",&a[i]);
	t=-1;
	for (i=0; i<n; i++)
		for (j=i; j<n; j++)
			for (k=j; k<n; k++) 
				if (a[i]+a[j]+a[k]<s1) {
					t++;
					s[t]=a[i]+a[j]+a[k];
				}
	qsort(s,t,sizeof(long),comp);
	ok=0;
	for (i=0; i<=t; i++) 
		if (cautare(s1-s[i])!=0) {
            s2=s[i];
            s3=s1-s2;			
			afis();
			ok=1;
			break;
		}
	return 0;
}