Cod sursa(job #202801)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 11 august 2008 17:08:36
Problema Ghiozdan Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<stdio.h>
#define INF 31005
#define N 80005
unsigned short v[N],nr[300],a[22222],t[N];
int main(){
	int x=0,i,j,k,n,g;
	freopen("ghiozdan.in","r",stdin);
	freopen("ghiozdan.out","w",stdout);
	scanf("%d%d",&n,&g);
	for(i=0;i<n;++i){
		scanf("%d",&k);
		nr[k]++;
	}
	n=0;
	for(i=250;i>0;--i)
		for(j=0;j<nr[i];++j)
			a[n++]=i;
	for(i=1;i<=g;++i)
		v[i]=INF;
	v[0]=0;
	for(i=0;i<n;i++){
		k=a[i];
		x+=k;
		if(x>g)
			x=g;
		for(j=x;j>=k;j--)
			if(v[j-k]+1<v[j]){
				v[j]=v[j-k]+1;
				t[j]=k;
			}
			if(v[g]<INF)
				break;
	}
	while(v[g]==INF)
		g--;
	printf("%d%d\n",g,v[g]);
	while(g){
		printf("%d\n",t[g]);
		g-=t[g];
	}
	return 0;
}