Cod sursa(job #592558)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 28 mai 2011 22:52:24
Problema Economie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct coin
{
    int val,ind;
};

struct cmp
{
    bool operator()(coin i,coin j)
    {
        return i.val<j.val;
    }
};

int o[50001],u[1001];
coin v[1001];

int main()
{
    int i,j,n,sol=1;
    freopen("economie.in","r",stdin);
    freopen("economie.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d",&v[i].val);
        v[i].ind=i;
    }
    sort(v+1,v+n+1,cmp());
    for (i=0;i<=50000;i+=v[1].val)
        o[i]=1;
    u[v[1].ind]=1;
    for (i=2;i<=n;++i)
        if (!o[v[i].val])
        {
            u[v[i].ind]=1;
            ++sol;
            for (j=0;j<=50000-v[i].val;++j)
                if (o[j])
                    o[j+v[i].val]=1;
        }
    printf("%d\n",sol);
    for (i=1;i<=n;++i)
        if (u[i])
            printf("%d\n",i);
    return 0;
}