Pagini recente » Clasament 16_februarie_simulare_oji_2024_clasele_11_12 | Cod sursa (job #1192240) | Cod sursa (job #1688911) | Cod sursa (job #2542087) | Cod sursa (job #2373921)
/**
* Soluția se bazează pe observația că dat fiind un număr N, este ușor
* să găsim numărul de zerouri al lui N!, prin împărțiri la puteri consecutive
* ale lui 5. Cu alte cuvinte, știind N putem afla P foarte rapid.
*
* În schimb, nu avem un mod la fel de simplu de a-l găsi pe N, dat fiind P. De
* aceea, ne vom folosi de o căutare binară pentru a-l „ghici” pe N. Luăm N ca
* fiind valoarea de mijloc a căutării, vedem câte zerouri are, dacă are fix P
* zerouri, atunci returnăm cel mai mare multiplu de 5 mai mic sau egal cu N,
* din moment ce N trebuie să fie minim.
*
* Pentru testele acestei probleme nu contează foarte mult ce limite inițiale
* folosim pentru căutare. Putem, de exemplu, să efectuăm căutarea în intervalul
* (1, 5 * 10^8), deoarece știm sigur că N se va afla acolo (P este maxim 10^8,
* iar un 5 în N! este echivalent cu un 0). O mică optimizare ar fi să folosim
* în schimb intervalul (P, 5 * P), dar oricare opțiune este suficientă pentru
* a trece toate testele.
*/
#include <bits/stdc++.h>
using namespace std;
// Calculează numărul de zerouri al lui n!, adică de câte ori apare 5 în produs.
int get_num_of_zeros(int n) {
int power = 5;
int num_of_zeros = 0;
while (power <= n) {
num_of_zeros += n / power;
power *= 5;
}
return num_of_zeros;
}
// Caută binar răspunsul N pentru o anumită valoare țintă (P).
void binary_search(int l, int r, int target) {
if (l > r) {
cout << "-1";
return;
}
int mid = (l + r) >> 1;
int num_of_zeros = get_num_of_zeros(mid);
// Dacă mid are câte zerouri ne trebuie, vom afișa cel mai mare multiplu de 5
// imediat sub el (sau chiar mid, dacă e divizibil cu 5), din moment ce ne
// trebuie cel mai mic N posibil.
if (num_of_zeros == target) {
mid -= mid % 5;
cout << mid;
} else if (num_of_zeros < target) {
binary_search(mid + 1, r, target);
} else {
binary_search(l, mid - 1, target);
}
}
int main() {
stdin = freopen("fact.in", "r", stdin);
stdout = freopen("fact.out", "w", stdout);
int P;
cin >> P;
// Tratăm separat cazul când P = 0. Altfel, efectuăm o căutare binară între
// P și P * 5.
if (P) {
binary_search(P, P * 5, P);
} else {
cout << "1";
}
}