După calificarea la campionatul european de fotbal din Franța, având în vizor N jucători din care trebuie să convoace câțiva în echipa națională, selecționerul României a apelat la niște metode mai puțin ortodoxe. Acesta a mers la vrăjitoarele renumite din Craiova pentru a-l ajuta să găsească formula câștigătoare pentru meciul de deschidere cu Franța. Vrăjitoarele, după descântece îndelungate, au ajuns la concluzia că lotul de jucători trebuie sa aibă valoarea exact X și coeficientul de aroganță cât mai mic. Valoarea unui lot de jucători e definită ca suma valorilor jucătorilor ce intră în componența lotului. Coeficientul de aroganță al unui lot de jucători e definit ca diferența dintre valoarea maximă a unui jucător din lot și valoarea minimă a unui jucător din lot. Se mai știe că valoarea lotului nu poate depăși o valoare cunoscută Vmax. Un lot de jucători e definit ca o submulțime nevidă de jucători aleși dintre cei N. Atenție, un lot poate fi format și dintr-un singur jucător.

Cerința

Se dă numărul N de jucători, numărul Vmax definit mai sus și valoarea fiecărui jucător. Selecționerul României a găsit formula câștigătoare și e curios dacă puteți și voi. Fiindcă nu are încredere totală în vrăjitoare, acesta vă cere să aflați pentru fiecare valoare X din intervalul [1,Vmax] coeficientul de aroganță minim posibil pentru care există cel puțin un lot dintre cei N jucători cu valoare exact X. Dacă nu se poate obține nici un lot de valoare exact X, se consideră ca răspuns -1.

Date de intrare

Fișierul de intrare euro.in conține pe prima linie T, reprezentând numărul de teste. În continuare vor urma T teste, fiecare având următoarea structură: pe prima linie dintr-un test se află N și Vmax, reprezentând numărul total de jucători, respectiv valoarea maximă pe care o poate avea un lot de jucători. A doua linie a testului conţine N numere naturale despărţite prin câte un spaţiu. Al i-lea număr de pe această linie reprezintă valoarea pe care o are al i-lea jucător.

Date de ieșire

În fișierul de ieșire euro.out se vor afișa T linii, câte una pentru fiecare test din fișierul de intrare. O linie corespunzătoare unui test conține Vmax numere (Vmax-ul testului curent), unde cel de-al i-lea număr reprezintă coeficientul de aroganță minim posibil pentru o submulțime de jucători de valoare exact i. În cazul în care nu există o submulțime de jucători de valoare exact i se afișează -1.

Restricții și precizări

1 ≤ T ≤ 2
1 ≤ N ≤ 4000
1 ≤ Vmax ≤ 8000
1 ≤ valoare[i] ≤ Vmax
Pentru 20% din teste N <= 20
Pentru 40% din teste N <= 100 și Vmax <= 100
Pentru 50% din teste N <= 300 și Vmax <= 300

Exemplu

euro.in

euro.out

-1 0 0 0 0 2 1 
0 0 0 2 1 0 5 0 3 5 4 5 6 2 7

Explicație

Pentru primul test:

Nu se poate găsi un lot de valoarea 1, deci răspunsul pentru 1 este -1.
Se pot obtine loturi de valoare 2, 3, 4, 5 dintr-un singur jucator.
Lotul de valoare 6 se poate obține din jucatorii cu valorile 2 si 4.
Pentru valoarea 7 exista doua loturi posibile formate din jucătorii cu valorile 5 2 respectiv 3 4. Cel din urma lot are coeficientul de aroganta mai mic (adică max(3,4)-min(3,4)=1).

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

#include <bits/stdc++.h>

using namespace std;

ifstream f("euro.in");
ofstream g("euro.out");

#define pb push_back
#define ll long long
#define mp make_pair

const int NMAX = 5005;
const int PMAX = 10005;
const int INF = (1 << 29);
const int nmax = 4000;
const int pmax = 8000;
int n, p, dp[2][PMAX];
int a[NMAX];
int ans[PMAX];
//set<int> mySet;

int main() {
    int t;
    f >> t;
    assert(t >= 1 && t <= 2);
    for (; t; --t) {
        f >> n >> p;
        assert(n >= 1 && n <= nmax);
        assert(p >= 1 && p <= pmax);
        for (int i = 1; i <= n; ++i) {
            f >> a[i];

            assert(a[i] <= p);
            assert(a[i] > 0);
            //assert(a[i] != 1);
        }

        sort(a + 1, a + n + 1);

        for (int i = 1; i <= p; ++i) {
            ans[i] = INF;
        }

        int prevLine = 0;
        for (int i = 0; i <= p; ++i) {
            dp[prevLine][i] = 0;
        }


        for (int i = 1; i <= n; ++i) {
            int currentLine = prevLine ^ 1;
            for (int j = 0; j <= p; ++j) {
                dp[currentLine][j] = dp[prevLine][j];
                if (j - a[i] >= 0) {
                    dp[currentLine][j] = max(dp[currentLine][j], dp[prevLine][j - a[i]]);
                }
            }
            dp[currentLine][a[i]] = a[i];
            for (int j = 1; j <= p; ++j) {
                if (dp[currentLine][j] != 0) {
                    ans[j] = min(ans[j], a[i] - dp[currentLine][j]);
                }
            }
            //cerr << i << " " << ans << " " << a[i] << " " << dp[i][p] << "
";
            prevLine = currentLine;
        }
        for (int i = 1; i <= p; ++i) {
            if (ans[i] == INF) {
                ans[i] = -1;
            }
            g << ans[i] << " ";
        }
        g << "
";
    }
    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 #1679 Euro

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