Cod sursa(job #355886)

Utilizator the1dragonIonita Alexandru the1dragon Data 12 octombrie 2009 15:37:03
Problema Loto Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<stdio.h>
#include<stdlib.h>
struct tip
{
	int v, c;
}vec[1024000];

int cmp(const void *a, const void *b)
{
	if (((tip *)a)->v > ((tip *)b)->v) return 1;
	else return -1;
}
int main()
{
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);
	int n, val[128], s, i, j, k, nivel=0, sol1=0, sol2=-1;
	bool gasit=false;
	
	scanf("%d%d", &n, &s);
	for (i=1; i<=n; i++)
		scanf("%d", &val[i]);
	for (i=1; i<=n; i++)
		for (j=i; j<=n; j++)
			for (k=j; k<=n; k++)
			{
				++nivel;
				vec[nivel].v=val[i]+val[j]+val[k];
				vec[nivel].c=i*1000000 + j*1000 + k;
			}
	qsort(vec+1, nivel, sizeof(tip), cmp);
	int st, dr, mij;
	for (i=1; (i*2<=nivel+1) && (gasit==false); i++)
	{
		sol1=i;
		st=1; 
		dr=nivel;
		while (st!=dr)
		{
			mij=(st+dr)/2;
			if (vec[mij].v >= s-vec[sol1].v)
				dr=mij;
			else
				st=mij+1;
		}
		if (vec[st].v+vec[sol1].v==s)
		{
			sol2=st;
			gasit=true;
		}
	}
	if (sol2!=-1)
		printf("%d %d %d %d %d %d", val[vec[sol1].c%1000], val[(vec[sol1].c/1000)%1000], val[vec[sol1].c/1000000], val[vec[sol2].c%1000], val[(vec[sol2].c/1000)%1000], val[vec[sol2].c/1000000]);
	else
		while (1);
	//	printf("-1");
	return 0;
}