Gigel are o bibliotecă cu T rafturi orizontale de diferite lungimi și T cutii cu cărți, câte o cutie pentru fiecare raft, în ordine. Cărţile dintr-o cutie au grosimi cunoscute și înălţimi egale cu înălţimea raftului pentru care sunt pregătite.

Gigel îşi doreşte foarte mult o bibliotecă nouă şi încearcă să o convingă pe mama sa folosind următoarea tactică: pe fiecare raft în parte el vrea să plaseze un număr minim de cărţi din cutia corespuzătoare astfel încât, așezându-le în anumite poziţii, să nu mai încapă nicio carte dintre cele rămase în acea cutie.

Cerința

Ajutați-l pe Gigel să determine, pentru fiecare raft, numărul minim de cărți ce pot fi alese din cutia corespunzătoare pentru a fi plasate pe raft în condițiile de mai sus.

Date de intrare

Fișierul de intrare carti.in conține pe prima linie numărul de rafturi T. Pe următoarele 2*T linii se găsesc informaţii despre rafturi și despre cărțile din cutiile corespunzătoare. Fiecare raft este descris pe două linii succesive: pe prima linie se află numerele N şi L separate printr-un singur spațiu, reprezentând numărul de cărți din cutie respectiv lungimea raftului. Pe a doua linie se află N numere naturale, separate printr-un singur spațiu, reprezentând grosimile celor N cărți din cutia corespunzătoare.

Date de ieșire

Fișierul de ieșire carti.out va conține T linii, câte una pentru fiecare raft. Pe fiecare linie va fi scris un singur număr ce reprezintă numărul minim de cărți plasate pe raftul respectiv în condițiile din enunț.

Restricții și precizări

1 ≤ T ≤ 13
1 ≤ L ≤ 10.000
1 ≤ N ≤ 100
Gigel nu are nicio carte mai lată decât raftul pe care ar putea fi aşezată
Distanţa dintre două cărţi consecutive plasate pe raft este un număr real pozitiv
Orice carte aleasă se plasează în poziție verticală în întregime în interiorul raftului
Modul de așezare pe raft este influențat doar de grosimea cărților
Pentru 10% din teste N ≤ 13
Pentru alte 15% din teste N ≤ 31 și L ≤ 100
Pentru alte 35% din teste L ≤ 500

Exemplu

carti.in

carti.out

4
1

Explicație

Cărţi alese pentru raftul 1: 1, 1, 4 şi 4
Cărţi alese pentru raftul 2: 4

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 carti:

#define TuTTy "Cosmin-Mihai Tutunaru"
#include <cstdio>
#include <algorithm>
#define infile "carti.in"
#define outfile "carti.out"
#define nMax 103
#define lMax 10013

using namespace std;

int dp[lMax];
int v[nMax];
int n, l;
int sol;

void read() {
    scanf("%d %d
", &n, &l);

    for (int i = 0; i < n; ++i) {
        scanf("%d", &v[i]);
    }
}

void solve() {

    sol = n;
    dp[0] = 0;
    sort(v, v+n);

    for (int i = 1; i <= l; ++i) {
        dp[i] = l;
    }

    for (int i = n-1; i >= 0; --i) {

        if (i < n-1) {
            for (int s = l; s >= v[i+1]; --s) {
                dp[s] = min(dp[s], dp[s - v[i+1]] + 1);
            }
        }

        int s = 0;

        for (int j = 0; j < i; ++j) {
            s += v[j];
        }

        for (int k = 0; k <= l; ++k) {
            if (dp[k] < l && k+s <= l && v[i] * (dp[k]+i+1) > l-k-s) {
                sol = min(sol, dp[k]+i);
            }
        }

    }

}

void write() {
    printf("%d
", sol);
}

int main() {
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    int t;
    scanf("%d
", &t);

    while(t--) {
        read();
        solve();
        write();
    }

    fclose(stdin);
    fclose(stdout);
    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 #614 carti

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #614 carti 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 #614 carti