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

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

Rezumat

Se dau nn numere prime a1,a2,,ana_1, a_2, \ldots, a_n ordonate strict crescător. Considerăm șirul strict crescător bb format din multiplii nenuli ai acestor numere. Multiplii comuni apar o singură dată. Să se determine al kklea termen din acest șir.

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

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

Problema Număr
#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(klogn)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 (ai,i)(a_i, i) La fiecare pas, scoatem din heap perechea minimă (x,i)(x, i) și inserăm înapoi perechea (x+ai,i)(x + a_i, i) Dacă xx e diferit de xxul de la pasul precedent, înseamnă că am generat un nou termen al șirului bb Dacă nu, decrementăm iteratorul, pentru că va trebui să facem un pas în plus pentru a ajunge la termenul kk

Problema Număr
#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(2nlogk)O(2^n \log k)

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

f(x)=[xa1]+[xa2]+[xa3][xa1a2][xa1a3][xa2a3]+[xa1a2a3]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

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii