Cod sursa(job #418477)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 15 martie 2010 22:12:27
Problema Factorial Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<stdio.h>
#include<math.h>

int put(int n) {
	int cnt=0;
	while(n%5==0) n/=5, ++cnt;
	return cnt;
}

int factzero(int n) {
	int i,cnt=0;
	for(i=5; i<=n; i+=5)
		cnt+=put(i);
	return cnt;
}

void cautB(int st, int dr, int nrzero, int &sol) {
	if(st>dr) return;
	
	int mij=(st+dr)/2,val=factzero(mij);
	
	if(val==nrzero) { 
		sol=mij;
		if(sol%5 != 0)
			while(sol%5 != 0) sol--;
		return;
	}
	
	if(val>nrzero) cautB(st,mij-1,nrzero,sol);
			  else cautB(mij+1,dr,nrzero,sol);
}


int main() {
	freopen("fact.in","r",stdin);
	freopen("fact.out","w",stdout);
	
	int nrzero,st,dr,mij,sol;
	
	scanf("%d",&nrzero);
	if(nrzero==0) { 
		printf("1\n"); 
		return 0; 
	}
	
	sol=-1;
	cautB(1,1<<21,nrzero,sol);
	
	printf("%d\n",sol);
	
	return 0;
}