Cod sursa(job #2662976)

Utilizator RaduZevriRadu Zevri RaduZevri Data 24 octombrie 2020 23:35:30
Problema Factorial Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 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 0 si 5*n
	int stanga = 0;
	int dreapta = 5*n;
	
	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 zeruri 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 este 30.
			fout<<(mid/5)*5;
			//Terminam excutia programului
			return 0;
		}
		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]
		
	}
	return 0;
}