Cod sursa(job #1702982)

Utilizator Bodo171Bogdan Pop Bodo171 Data 15 mai 2016 21:22:58
Problema Ghiozdan Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
vector<int> rasp;
int i,j,reff[75005],gr,gtot,cnt,x,n,ap[205],mn;
ifstream f("ghiozdan.in");
ofstream g("ghiozdan.out");
//solutie "greedinamica"
//worst case performance (N*G)
void afis()
{
   g<<x<<' ';
    while(x!=0)
    {
        rasp.push_back(reff[x]);
        x-=reff[x];
    }
    g<<rasp.size()<<'\n';
    for(i=0;i<rasp.size();i++)
        g<<rasp[i]<<'\n';
}
int main()
{

    f>>n>>gr;mn=200;
    for(i=1;i<=n;i++)
    {
        f>>x;
        ap[x]++;
        gtot+=x;
        if(x<mn) mn=x;
    }
    reff[0]=-1;
    for(i=200;i>=1;i--)
      for(cnt=1;cnt<=ap[i];cnt++)
         for(j=gr-i;j>=0;j--)
    {
        if(reff[j+i]==0&&reff[j]!=0)
        {
            reff[j+i]=i;
            if(gr-(j+i)<mn||j+i==gtot)
            {
                x=j+i;
                afis();//am gasit un raspuns
                //cu obiecte de valori maxime,deci numar minim
                return 0;
            }
        }
    }
    return 0;
}