Cod sursa(job #14783)

Utilizator vmaneavmanea vmanea Data 9 februarie 2007 20:06:10
Problema Loto Scor 5
Compilator c Status done
Runda Arhiva de probleme Marime 3.31 kb
#include <stdio.h>
#include <stdlib.h>
#define nmax 105
#define sase 8

int N,S,i,j,k,t1,t2,t3,x,vv,ok,f;
int V[nmax], X[nmax], nr[sase];

struct nod
{
	int val;
	int st;
	int dr;
	int rc;
	int nr;
}

*ac[sase];

void msort(int, int);
void insereaza(int, int, int, int);
int cauta(int, int);
void recursie(int, int);


int main(void)
{
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);

	scanf("%d%d", &N, &S);
	for (i = 1; i <= N; ++i)
		scanf("%d", &V[i]);

	msort(1, N);

	for (i = (k = 0) + 1; i <= N; ++i)
		if (V[i] != V[i - 1])
			X[++k] = V[i];

	N = k;

	// initializez arborele de cautare de tip 0

	for (i = 0; i < 7; ++i)
	{
		++nr[i];

		ac[i] = (struct nod *)realloc(ac[i], (1+nr[i]) * sizeof(struct nod));
		ac[i][nr[i]].val = ac[i][nr[i]].st = ac[i][nr[i]].dr = 0;
		ac[i][nr[i]].nr = ac[i][nr[i]].rc = 0;
	}

	for (i = 1; i <= N; ++i)
	 for (t2 = 1; t2 <= 6; ++t2)
		insereaza(i, 0, 1, t2);

	for (f = 2; f <= 6; ++f)
	 for (t1 = 1; t1 < f; ++t1)
	  for (j = 2; j <= nr[t1]; ++j)
	   for (i = 1; i <= N; ++i)
		insereaza(i, t1, j, f-t1);

	x = (k = 0) + cauta(6, S);

	if (x == -1) printf("%d\n", x);

	else

	{
		recursie(6, S);

		for (i = 6; i > 1; --i)
			printf("%d ", V[i]);

			printf("%d\n", V[i]);

	}

	return 0;
}

void msort (int l, int r)
{
	int m = (l + r) >> 1, k, i, j;

	if (l >= r) return;

	msort(l, m);
	msort(m + 1, r);

	for (i = k = l, j = m + 1; i <= m && j <= r; ++k)
		if (V[i] <= V[j])
			X[k] = V[i++];
		else
			X[k] = V[j++];

	for (; i <= m; ++i)
		X[k++] = V[i++];

	for (; j <= r; ++j)
		X[k++] = V[j++];

	for (i = l; i <= r; ++i)
		V[i] =X[i];
}

void insereaza(int i, int t1, int j, int t2)
{
	t3 = t1 + t2;
	vv = X[i] * t2 + ac[t1][j].val;
	if (vv <= S)
	{


	for (x = ok = 1; ok; )
	{
		if (ac[t3][x].val == vv)
			ok = 0; // este deja pus
		else
		{
			if (ac[t3][x].val > vv)
			{
				if (ac[t3][x].st == 0)
				{
					++nr[t3];
					ac[t3] = (struct nod *)realloc(ac[t3], (1 + nr[t3]) * sizeof(struct nod));
					ac[t3][nr[t3]].val = vv;
					ac[t3][nr[t3]].st = 0;
					ac[t3][nr[t3]].dr = 0;
					ac[t3][nr[t3]].nr = t2;
					ac[t3][nr[t3]].rc = X[i];
					ac[t3][x].st = nr[t3];
					ok = 0;
				}
				else
					x = ac[t3][x].st;
			}
			else
			{
				if (ac[t3][x].dr == 0)
				{
					++nr[t3];
					ac[t3] = (struct nod *)realloc(ac[t3], (1 + nr[t3]) * sizeof(struct nod));
					ac[t3][nr[t3]].val = vv;
					ac[t3][nr[t3]].st = 0;
					ac[t3][nr[t3]].dr = 0;
					ac[t3][nr[t3]].nr = t2;
					ac[t3][nr[t3]].rc = X[i];
					ac[t3][x].dr = nr[t3];
					ok = 0;
				}
				else
					x = ac[t3][x].dr;
			}
		}
	}
	}
}

int cauta(int t3, int vv)
{
	for (x = 1, ok = 0; !ok; )
	{
		if (ac[t3][x].val == vv)
			ok = x; // am gasit
		else
		{
			if (ac[t3][x].val > vv)
			{
				if (ac[t3][x].st == 0)
					ok = -1;
				else
					x = ac[t3][x].st;
			}
			else
			{
				if (ac[t3][x].dr == 0)
					ok = -1;
				else
					x = ac[t3][x].dr;
			}
		}
	}

 return ok;
 // returneaza bre!!

}

void recursie(int t3, int vv)
{
	int x, i;

	if (t3 == 0)
		return;

	x = cauta(t3, vv);

	recursie(t3 - ac[t3][x].nr, vv - ac[t3][x].rc * ac[t3][x].nr);

	for (i = 1; i <= ac[t3][x].nr; ++i)
		V[++k] = ac[t3][x].rc;
}