👤
STEFANIARZE
a fost răspuns

Buna!! Ma puteti ajuta si pe mine cu problema "Bete" de pe pbinfo.ro, va rog? Imi da doar 30. Asta e sursa pe care am trimis-o
#include<fstream>
using namespace std;
ifstream f("bete.in");
ofstream g("bete.out");
int n, max1,v[101], s, p[10001], k, a[101];
int main ()
{
f>>n>>s;
max1 =0;
k=max1;
p[0]=-1;
for (int i=1;i<=n; ++i)
    f>>v[i];
for (int i=1; i<=n; ++i)
{
     for (int j=max1; j>=0; --j)
{
          if (p[j]!=0 && j+v[i]<=s)
                  p[j+v[i]]=i;
          if (k k=j+v[i];
}
max1 =k;
}
if(p[s]!=0)
{
     g<<"DA\n";
     k=0;
     while (p[s]>=0)
{
       k++;
       a[k]=v[p[s]];
       s-=v[p[s]];
}
g<<k<<'\n';
for (int i=1; i<=k; ++i)
g<<a[i]<<' ';        }
else
g<<"NU\n";
g.close();
return 0;
}

Răspuns :

EXPRESSZE
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
using namespace std;
#define NN 105
#define SS 105*100+10

ifstream fin("bete.in");
ofstream fout("bete.out");

int n, S, B[NN], v[SS], last[SS], smax;

void determinare(int i, int contor)
{
if(i==0)
fout << contor << "\n";
else
{
determinare(i-B[last[i]], contor+1);
fout << last[i] << " ";
}

}

int main(){
assert(fin >> n >> S );
for(int i=1 ; i<=n ; ++i)
assert(fin >> B[i]), assert(B[i]<100), smax += B[i];
if(S > smax)
{
fout << "NU";
return 0;
}

v[0] = 1;
for(int i=1;i<=n;++i)
for(int j=smax ; j>=0 ; --j)
if(v[j] && !v[j+B[i]])
v[j+B[i]] = 1, last[j+B[i]] = i;
//for(int i=0; i<=smax; ++i)
// cout << i << " " << v[i] << " " << last[i] << endl;


if(!v[S])
fout << "NU\n";
else
{
fout << "DA\n";
determinare(S, 0);
}

return 0;
}
Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Ne dorim ca informațiile furnizate să vă fi fost utile. Dacă aveți întrebări sau aveți nevoie de suport suplimentar, nu ezitați să ne contactați. Revenirea dumneavoastră ne bucură, iar pentru acces rapid, adăugați-ne la favorite!


Ze Lesson: Alte intrebari