Problema Număr – OJI 2008, Clasa a 11-a
Rezumat
Se dau numere prime ordonate strict crescător. Considerăm șirul strict crescător format din multiplii nenuli ai acestor numere. Multiplii comuni apar o singură dată. Să se determine al lea termen din acest șir.
Soluție
Încercăm să generăm șirul termen cu termen. Considerăm un vector unde reprezintă cel mai mare multiplu al lui generat până acum. Inițial, toate elementele lui sunt La fiecare pas, îl parcurgem pe și calculăm minimul al valorilor Acesta va fi noul termen al șirului Este posibil ca acest număr să fie multiplu a mai multe numere din șirul așa că trebuie să parcurgem din nou vectorul și să actualizăm toate valorile pentru care Repetăm procedeul până ajungem la termenul 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
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 La fiecare pas, scoatem din heap perechea minimă și inserăm înapoi perechea Dacă e diferit de ul de la pasul precedent, înseamnă că am generat un nou termen al șirului Dacă nu, decrementăm iteratorul, pentru că va trebui să facem un pas în plus pentru a ajunge la termenul
#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
Există și o soluție exponențială, care din cauza valorii maxime a lui nu poate fi folosită aici, dar merită menționată. Putem căuta binar termenul La fiecare pas din căutarea binară calculăm numărul de termeni ai șirului mai mici sau egali cu valoarea curentă Să notăm asta cu În funcție de vom continua căutarea în dreapta sau în stânga. Valoarea poate fi calculată folosind principiul includerii și excluderii. De exemplu, pentru avem:
Dacă ai vreo nedumerire cu privire la problema Număr, lasă un comentariu și te voi ajuta