Question

Gigel a primit cadou n bețe de diferite lungimi. Neștiind ce să facă cu ele, se întreabă dacă poate alege dintre bețele date o parte, astfel încât, lipindu-le, să obțină un băț de lungime S.
Date de intrare

Fişierul de intrare bete.in conţine pe prima linie numerele n S, separate printr-un spațiu, iar pe a doua linie n numere naturale separate prin spaţii, reprezentând lungimile bețelor.
Date de ieşire

Fişierul de ieşire bete.out va conţine pe prima linie mesajul DA, dacă pot fi alese bețe astfel încât lungimea totală a lor să fie S, și NU în caz contrar. Dacă este posibilă alegerea bețelor, urmează o alegere posibilă: pe linia a doua a fișierului se va afla un număr m, numărul de bețe alese; pe linia a treia se vor afla m numere distincte cuprinse între 1 și n, reprezentând numerele de ordine ale bețelor alese astfel încât suma lungimilor să fie S.
Restricţii şi precizări

1 ≤ n ≤ 100
numerele de pe a doua linie a fişierului de intrare vor fi numere naturale nenule mai mici decât 100

Exemplu 1:

bete.in

5 10
1 5 3 6 8

bete.out

DA
3
1 3 4

Exemplu 2:

bete.in

5 21
1 5 3 6 8

bete.out

NU

Answer 1

Ai sursa oficiala C++ a acestei probleme. Succes!
#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;
}