Cod sursa(job #883787)

Utilizator david_raucaRauca Ioan David david_rauca Data 20 februarie 2013 13:09:30
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#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;
}