Cod sursa(job #299721)

Utilizator lucaz0rLuca Liviu lucaz0r Data 6 aprilie 2009 22:33:19
Problema Economie Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <stdlib.h>
int sort_function (const void *a, const void *b)
{ return (*(long*)a-*(long*)b);
}
 


int main() {

	long n,min,i,j,val[1001],ok,sol[1001],crt;
	char a[50001];

	freopen ("economie.in","r",stdin);
	freopen ("economie.out","w",stdout);

	scanf ("%ld\n",&n);
	for (i = 1; i <= n; i++) scanf ("%ld",&val[i]);


	qsort ((void*)(val+1), n, sizeof(long), sort_function);

	//for (i = 1; i <=n; i++) printf ("%ld ",val[i]);
	//printf ("\n");

	for (i = 1; i <= val[n]; i++) a[i] = 0;

	min=1; sol[1]=val[1]; a[val[1]]=1;

	for (i = 2; i <= n; i++) if (val[i]!=val[1]) { crt=i;
						       break; }


	for (i = val[1]+1; i <= val[n]; i++) {
	  ok = 0;

		for (j = 1; j <= min; j++)
			if (a[i-sol[j]]==1) { ok=1;
					     a[i]=1;
					     break; }

		if (( ok == 0) && (val[crt]==i)) { min++;
						    sol[min]=val[crt];
                a[val[crt]] = 1;
						    for (j=crt; j<=n;j++)
							if (val[j]!=val[crt]) {crt=j;
									       break;}
						   }





              }





   printf ("%ld\n",min);
   for (i = 1; i <= min; i++) printf ("%ld\n",sol[i]);




	return 0;}