Rezumat Număr

Se dau $n$ numere prime $a_1, a_2, \ldots, a_n$ ordonate strict crescător. Considerăm șirul strict crescător $b$ format din multiplii nenuli ai acestor numere. Multiplii comuni apar o singură dată. Să se determine al $k$-lea termen din acest șir.

Soluție $O(k \cdot n)$

Încercăm să generăm șirul $b$ termen cu termen. Considerăm un vector $x$, unde $x_i$ reprezintă cel mai mare multiplu al lui $a_i$ generat până acum. Inițial, toate elementele lui $x$ sunt $0$. La fiecare pas, îl parcurgem pe $x$ și calculăm minimul $m$ al valorilor $x_i + a_i$. Acesta va fi noul termen al șirului $b$. Este posibil ca acest număr să fie multiplu a mai multe numere din șirul $a$, așa că trebuie să parcurgem din nou vectorul $x$ și să actualizăm toate valorile $x_i$ pentru care $x_i + a_i = m$. Repetăm procedeul până ajungem la termenul $k$, pe care-l afișăm.

#include <bits/stdc++.h>
using namespace std;

ifstream fin("numar.in");
ofstream fout("numar.out");

int main() {
    int n, k; fin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        fin >> a[i];
    vector<int> x(n);
    for (int i = 0; i < n; i++)
        fin >> x[i];

    int mn = 0;
    for (int i = 0; i < k; i++) {
        mn = 1e9;
        for (int j = 0; j < n; j++)
            mn = min(mn, x[j] + a[j]);
        for (int j = 0; j < n; j++)
            if (x[j] + a[j] == mn)
                x[j] += a[j];
    }
    fout << mn << '\n';

    fout.close();
    return 0;
}

Soluție $O(k \log n)$

Cu toate că restricțiile problemei îi permit soluției precedente să obțină punctaj maxim, o putem optimiza folosind un min-heap. Inserăm într-un min-heap perechi de forma $(a_i, i)$. La fiecare pas, scoatem din heap perechea minimă $(x, i)$ și inserăm înapoi perechea $(x + a_i, i)$. Dacă $x$ e diferit de $x$-ul de la pasul precedent, înseamnă că am generat un nou termen al șirului $b$. Dacă nu, decrementăm iteratorul, pentru că va trebui să facem un pas în plus pentru a ajunge la termenul $k$.

#include <bits/stdc++.h>
using namespace std;

ifstream fin("numar.in");
ofstream fout("numar.out");

int main() {
    int n, k; fin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        fin >> a[i];

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 0; i < n; i++)
        pq.emplace(a[i], i);

    int prev = 0;
    for (int i = 0; i < k; i++) {
        auto top = pq.top(); pq.pop();
        if (top.first == prev)
            i--;
        else
            prev = top.first;
        top.first += a[top.second];
        pq.push(top);
    }
    fout << prev << '\n';

    fout.close();
    return 0;
}

Soluție $O(2^n \log k)$

Există și o soluție exponențială, care din cauza valorii maxime a lui $n$ nu poate fi folosită aici, dar merită menționată. Putem căuta binar termenul $k$. La fiecare pas din căutarea binară calculăm numărul de termeni ai șirului $b$ mai mici sau egali cu valoarea curentă $x$. Să notăm asta cu $f(x)$. În funcție de $f(x)$, vom continua căutarea în dreapta sau în stânga. Valoarea $f(x)$ poate fi calculată folosind principiul includerii și excluderii. De exemplu, pentru $n = 3$, avem:

$$f(x) = \left[ \frac{x}{a_1} \right] + \left[ \frac{x}{a_2} \right] + \left[ \frac{x}{a_3} \right] - \left[ \frac{x}{a_1 a_2} \right] - \left[ \frac{x}{a_1 a_3} \right] - \left[ \frac{x}{a_2 a_3} \right] + \left[ \frac{x}{a_1 a_2 a_3} \right]$$

Dacă ai vreo nedumerire cu privire la problema Număr, lasă un comentariu și te voi ajuta :)

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație!

PayPal