👤
a fost răspuns

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

Răspuns :

EXPRESSEZ
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;
}

Vă mulțumim că ați vizitat platforma noastră dedicată Informatică. Sperăm că informațiile oferite v-au fost utile. Dacă aveți întrebări sau aveți nevoie de asistență suplimentară, nu ezitați să ne contactați. Așteptăm cu nerăbdare să vă revedem și nu uitați să ne salvați în lista de favorite!


Ez Askings: Alte intrebari