Problema Număr – OJI 2008, Clasa a 11-a

• Dificultate:
• Autor: Stelian Ciurea
• Online: InfoArena, PbInfo

Rezumat

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';
   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';
   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:

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