Cod sursa(job #418488)

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

int factzero(int n) {
	//round(n/5) + round(n/25) + round(n/125)+.......+round(n/5^n)
	int i=1, termen, sum=0;
	do {
		termen=n/pow(5,i);
		sum+=termen;
		i++;
	} while(pow(5,i)<=n);
	
	return sum;
}

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<<25,nrzero,sol);
	
	printf("%d %d\n",sol,factzero(45));
	
	return 0;
}