Nu aveti permisiuni pentru a descarca fisierul grader_test8.ok
Cod sursa(job #1510036)
| Utilizator | Data | 24 octombrie 2015 15:04:37 | |
|---|---|---|---|
| Problema | Factorial | Scor | 85 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 1.23 kb |
#include <fstream>
using namespace std;
ifstream fin("fact.in");
ofstream fout("fact.out");
int p;
int powFiveSmallerThanX(int x) {
int n = 5, pow = 1;
while (n <= x) {
++pow;
n *= 5;
}
--pow;
return pow;
}
int howManyFives(int x) {
int w = 5, s = 0;
for (int i = 1; i <= powFiveSmallerThanX(x); ++i) {
s += x / w;
w *= 5;
}
return s;
}
void binarySearch() {
int lmtL = 5, lmtR = p * 5;
int pivot = (lmtL + lmtR) / 2;
while (true) {
if (howManyFives(pivot) >= p) {
lmtR = pivot;
pivot = (lmtL + lmtR) / 2;
if (lmtL == lmtR - 1) {
while (lmtR % 5 != 0)
--pivot;
fout << lmtR;
return;
}
}
else if (howManyFives(pivot) < p) {
lmtL = pivot;
pivot = (lmtL + lmtR) / 2;
if (lmtL == lmtR - 1) {
fout << lmtR;
return;
}
}
}
/*while (pivot % 5 != 0)
--pivot;
fout << pivot;*/
}
int main()
{
fin >> p;
if (p == 0) fout << 1;
else binarySearch();
return 0;
}
