Cod sursa(job #2662986)

Utilizator RaduZevriRadu Zevri RaduZevri Data 25 octombrie 2020 00:03:46
Problema Factorial Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>

using namespace std;

int zerouri(int nr){
	int nr_zerouri = 0;
	while(nr>0){
		nr/=5;
		nr_zerouri+=nr;
	}
	return nr_zerouri;
}

int main(){
	ifstream fin("fact.in");
	ofstream fout("fact.out");
	
	int n;
	fin>>n;
	
	// Numarul pe care il cautam este mereu intre stanga si dreapta
	// Initial, stim sigur ca e intre 1 (strict pozitiv) si 5*n
	int stanga = 1;
	int dreapta = 5*n;

	int numar_gasit = -1; //Initial -1, in caz ca nu gasim
	
	while(stanga<=dreapta){
		int mid = (dreapta+stanga)/2;
		int nr_de_0 = zerouri(mid);
		
		//Debugging
		//fout<<stanga<<" "<<mid<<" "<<dreapta<<" "<<nr_de_0<<"\n";
		
		if(nr_de_0==n){
			//Are numarul de zerouri pe care il vrem
			//Noi vrem cel mai mic numar, deci cel mai mare numar care se imparte la 5
			//De exemplu, 34 are 7 de 0, dar cel mai mic nr cu 7 de 0 eiste 30.
			numar_gasit = mid-mid%5;
			//Terminam while loopul
			stanga = dreapta+1;
		}
		else if (nr_de_0<n) stanga=mid+1; //Cautam in intervalul [mid+1,dreapta]
		else dreapta = mid-1;//Numarul e prea mare, cautam in [stanga,dreapta-1]
		
	}
	fout<<numar_gasit<<"\n";

	return 0;
}