Cod sursa(job #137955)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 17 februarie 2008 18:05:50
Problema Economie Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdio.h>
int v[50005],w[100000],n,k=0;
int caut(int s){
	int i,j,u[52000];
	u[0]=1;
	for (i=1;i<=k;i++)
		for(j=0;j<=v[n];j++)
			if(u[j]) { u[j+w[i]]=1; if(j+w[i]==s) return 1;}
	return 0;
}
int main(){
	int i,inj,gata,aux,ok;
	FILE*f=fopen("economie.in","r");
	FILE*g=fopen("economie.out","w");
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&v[i]);
	inj=n;
	while(inj>1){
		inj/=2;
		do {
			gata=1;
			for(i=1;i<=n-inj;i++)
				if(v[i]>v[i+inj]){
					aux=v[i];
					v[i]=v[i+inj];
					v[i+inj]=aux;
					gata=0;
				}
		}
		while(!gata);
	}
	w[++k]=v[1];
	for(i=2;i<=n;i++){
		ok=caut(v[i]);
		if(!ok) w[++k]=v[i];
	}
	fprintf(g,"%d\n",k);
	for(i=1;i<=k;i++)
		fprintf(g,"%d\n",w[i]);
	return 0;
}