Cerinţa

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Bete:

#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 << "
";
    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
";
    else
    {
        fout << "DA
";
        determinare(S, 0);
    }
    
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #402 Bete

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #402 Bete de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #402 Bete