Cod sursa(job #137959)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 17 februarie 2008 18:17:56
Problema Economie Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
int v[2005],w[2005],n,k=0;
int caut(int s){
	int i,j,u[100000];
	u[0]=1;
	for (i=1;i<=k;i++)
		for(j=0;j<=v[n];j++)
			if(u[j] && j+w[i]<=v[n]) { u[j+w[i]]=1; if(j+w[i]==s) return 1;}
	return 0;
}
int main(){
	int i,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]);
	sort(v+1,v+n+1);
	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;
}