Pagini recente » Cod sursa (job #417709) | Cod sursa (job #528771) | Cod sursa (job #3005594) | Cod sursa (job #204402) | Cod sursa (job #883787)
Cod sursa(job #883787)
#include<fstream>
using namespace std;
#define INF 1000000000000000000LL
ifstream fin("fact.in");
ofstream fout("fact.out");
long long p; // Numarul de 0-ouri
long long rasp; // Numarul cautat - raspunsul
void CautareBinara(long long st, long long dr); // Functia care cauta binar numarul, st - numarul cel mai mic al intervalului, dr - nr cel mai mare al intervalului
bool OK(long long x); // Functia care valideaza daca factorialul numarului contine numarul p de zero-uri la sfarsit
int main()
{
fin >> p; // Citim p - numarul de zero-uri
CautareBinara(1, INF); // Incercam sa nimerim raspunsul corect - stim ca numarul se afla in intervalul 1, INF
fin.close();
fout.close();
return 0;
}
void CautareBinara(long long st, long long dr)
{
if( st >= dr ) // conditia de iesire - daca intervalul contine doar un element sau nici unul
{
if( rasp != 0 ) // daca in pasii anteriori am gasit un raspuns il afisam
fout << rasp;
else // daca nu afisam -1
fout << -1;
return;
}
long long mij = (st + dr) >> 1; // obtinem numarul din mijloc al intervalului
if( OK(mij) == 1 ) // daca numarul de 0-uri ale numarului este mai mic decat p atunci rezultatul se gaseste in intervalul superior
CautareBinara( mij + 1, dr ); // adica mij + 1, dr
else // daca numarul de 0-uri ale numarului este mai mare atunci rezultatul se afla in intervalul inferior
CautareBinara( st, mij ); // daca numarul contine p-zerouri cautam un numar mai mic cu acelasi numar de zero-uri in intervalul inferior
}
bool OK( long long x )
{
// Pentru ca numai 2*5 formeaza un 0 la sfarsitul rezultatului, multiplii de 2 fiind mai multi, ne ramane sa numaram cate
// numere cu 5 in coada sunt in factorialul numarului
long long aux = x; // aux = copia lui x
long long nrZero = 0; // nrZero = numarul de 0-uri din numar
while( aux / 5 != 0 )
{
aux /= 5; // impartim repetat numarul la 5 cat timp obtinem catul diferit de 0
nrZero += aux; // adaugam catul impartirii la 5 la numarul de zero-uri = numarul de multiplii de 5 ai catului
}
if( nrZero == p )
{
rasp = x;
return 0;
}
if( nrZero < p )
return 1;
return 0;
}