Cod sursa(job #13920)

Utilizator peanutzAndrei Homorodean peanutz Data 7 februarie 2007 19:52:28
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdlib.h>
#include <stdio.h>

#define NMAX 110

long a[NMAX];
long uz[NMAX];
long n, s;
long sol[10];
long suma;

void read()
{
int i;

scanf("%ld %ld\n", &n, &s);

for(i = 0; i < n; ++i)
	scanf("%ld ", &a[i]);
}

void sort()
{
int i, cod, aux;

do
	{
		cod = 0;

		for(i = 0; i < n-1; ++i)
			if(a[i] > a[i+1])
				{
					aux = a[i];
					a[i] = a[i+1];
					a[i+1] = aux;

					cod = 1;
				}
	}	while(cod);
}

void abort_it(long x)
{
int cod = 1, i;

for(i = 0; i < 5; ++i)
	{
		if(x < a[i]  &&  cod)
			cod = 0, printf("%ld ", x);

		else
			printf("%ld ", a[sol[i]]);
	}
printf("\n");

fclose(stdin);
fclose(stdout);

exit(0);


}


void back(int k)
{
long i, m, st, dr, x;

if(k == 5)
	{
		x = s-suma;

		st = 0;
		dr = n-1;

		while(st <= dr)
			{
				m = (st+dr)/2;

				if(a[m] == x)
					abort_it(a[m]);

				else if(x > a[m])
					st = m+1;

				else
					dr = m-1;
			}

	}

else
	{
		for(i = 0; i < n; ++i)
			{
				if(!uz[i]  &&  suma+a[i] <= s)
					{
						suma += a[i];

						sol[k] = i;

						back(k+1);

						suma -= a[i];

					}
			}
	}
}

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

read();


sort();


back(0);


printf("-1\n");


fclose(stdin);
fclose(stdout);

return 0;
}