Cod sursa(job #144386)

Utilizator MarquiseMarquise Marquise Data 27 februarie 2008 15:52:46
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <stdio.h>

#define NMAX 105
#define VMAX 1000005

int n, x[NMAX], v[VMAX], p[NMAX], num, S;


int partitie(int st, int dr)
{
	int i, j, aux, pivot;
	i = st - 1;
	j = dr + 1;
	pivot = v[(st + dr) / 2];
	while (1)
	{
		do { ++i;} while ( v[i] < pivot);
		do { --j;} while ( v[j] > pivot);
		if ( i < j)
		{
			aux = v[i];
			v[i] = v[j];
			v[j] = aux;
			aux = p[i];
			p[i] = p[j];
			p[j] = aux;
		}
		else
			return j;
	}

}



void sort(int st, int dr)
{
	int m;
	if ( st < dr)
	{
		m = partitie(st, dr);
		sort(st, m);
		sort( m + 1, dr);
	}
}

int caut(int val)
{
	int st, dr, m;
	st = 1;
	dr = num;
	while ( st <= dr)
	{
		m = ( st + dr) / 2;
		if ( v[m] == val)
			return m;
		else
		{
			if ( v[m] > val)
				dr = m - 1;
			else
				st = m + 1;
		}
	}

	return 0;
}

void pozitii(int p)
{
	int c, r;

	c = p / (n * n);
	r = p % (n * n);
	printf("%d ", x[c + ( r != 0)] );
	if ( r == 0)
		printf("%d %d ", x[n], x[n]);
	else
	{
		p = r;
		c = p / n;
		r = p % n;
		printf("%d ", x[c + (r !=0 )]);
		if ( r == 0)
			printf("%d ", x[n]);
		else
			printf("%d ", x[r]);
	}
}

int main()
{
	int i, j, k, ex, tr;
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);
	scanf("%d %d", &n, &S);
	for ( i = 1; i <= n; i++)
		scanf("%d", &x[i]);
	for ( i = 1; i <= n; i++)
	for ( j = 1; j <= n; j++)
	for ( k = 1; k <= n; k++)
		v[++num] = x[i] + x[j] + x[k];

	for ( i = 1; i <= num; i++)
		p[i] = i;

	sort(1, num);

	tr = 1;
	for ( i = 1; i <= num && tr; i++)
	{
		ex = caut( S - v[i]);
		if ( ex )
		{
			pozitii(p[i]);
			pozitii(p[ex]);
			tr = 0;
		}
	}
	if ( tr)
		printf("-1\n");
	return 0;
}