Cod sursa(job #697276)

Utilizator IronWingVlad Paunescu IronWing Data 29 februarie 2012 00:02:33
Problema Factorial Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#define MAX_N 999999999
/* This program determines the first n such n! has exactly p trailing zeros.
 * It computes it, using binary search and a mathematical formula for determining the number of trailing 0's of n!.
 */

/* function which return the number of zeros of n!, with n as argument */ 
int noZeros(int n){
	int zeros = 0, fives = 5, div;
	while((div = n / fives) != 0){
		zeros += div;
		fives *= 5;
	}
	return zeros;
}

/* function which determines the n for which n! has p trailing zeros, using binary search algorithm */
int determineFact(int p){
	int min = 0, max = MAX_N, med, zeros, val = -1;
	while(min <= max){
		/* invariant: if a[i]==val for any i, then lower <= i <= upper */
		med = min + (max - min)/2;
		zeros= noZeros(med);
		if(zeros >= p){
			max = med - 1;
		}
		else {
			min = med + 1;
		}
	}
	return zeros == p ? min : -1;
}

int main(){
	freopen("fact.in", "r", stdin);
	freopen("fact.out", "w", stdout);
	int p, n;
	scanf("%d", &p); // read the number of zeros
	fclose(stdin);
	if(p == 0){
		putchar('1');
		return 0;
	}
	n = determineFact(p);	
	printf("%d",n);	
	fclose(stdout);
	return 0;
}