Cod sursa(job #109717)

Utilizator DranaXumAlexandru Dumitru Paunoiu DranaXum Data 25 noiembrie 2007 12:32:31
Problema Economie Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 1, Clasa a 10-a Marime 1.11 kb
#include<stdio.h>
#include<string>

using namespace std;

int x[50001],p[50001];

void Qsort1(int l, int u)
{
    int i,m;
    if(l>=u) return;
    m=l;
    for(i=l+1;i<=u;i++){
        if(x[i]<x[l]){m++; 
        swap(x[m],x[i]);
        }
    }
    swap(x[l],x[m]);
    Qsort1(l,m-1);
    Qsort1(m+1,u);
}

int main()
{
    int n,i,j;
    FILE *fin,*fout;
    fin=freopen("economie.in","r",stdin);
    fout=freopen("economie.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x[i]);
    }
    Qsort1(1,n);
    int cnt=0;
    for(i=n;i>=1;i--)
    {
        j=i;
        if(p[i]!=1)
        {
            int aux=x[i];
            while(aux && j>0)
            {
                j--;
                while(aux>=x[j])
                {   
                    aux-=x[j];
                    if(!p[j]){p[j]=1; cnt++;}    
                }
                
            }
        }
    }
    printf("%d\n",cnt);
    for(i=1;i<=n;i++)
        if(p[i])
            printf("%d\n",x[i]);
    fclose(fin);
    fclose(fout);
    return 0;    
}