Cod sursa(job #286740)

Utilizator eugen.nodeaEugen Nodea eugen.nodea Data 24 martie 2009 09:37:46
Problema Economie Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
# include <stdio.h>     
int N,i,v[1001],S[50001],k,j;   
void quick(int st, int dr)   
{   
  int i=st,j=dr,p=v[(st+dr)/2],aux;   
  if (dr<=st) return;   
  while (i<=j){   
    while (v[i]<p) i++;   
    while (p<v[j]) j--;   
    if (i<=j) {   
    aux=v[i];v[i]=v[j]; v[j]=aux;   
    i++; j--;   
    }   
  }   
  if (st<j) quick(st,j);   
  if (i<dr) quick(i,dr);   
}   
int main(){   
  freopen("economie.in", "r", stdin);   
  freopen("economie.out", "w", stdout);   
  scanf("%d",&N);   
  for (i=1;i<=N;++i)  
    scanf("%d",&v[i]);   
  quick(1,N);   
  for (i=1,k=0;i<=N;i++){
	if (S[v[i]]==0) S[v[i]]=2,k++; 
    for (j=v[i]+1;j<=v[N];j++)
		   if (S[j-v[i]]!=0)S[j]=1;
    }
    printf("%d\n",k);
	for (i=1;i<=N;i++)
		if (S[v[i]]==2) printf("%d\n",v[i]);	
    return 0; 
}