Cod sursa(job #1199006)

Utilizator dorinmoldovanMoldovan Dorin dorinmoldovan Data 17 iunie 2014 22:17:08
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include "stdio.h"
#include "stdlib.h"

#define N 500000000

int A[20];
int length = 0;

int getNoOfZeros(int n)
{
	int sum = 0;
	for(int i = 0; i < length; i++){
		sum = sum + n / A[i];
	}
	return sum;
}

int search(int left, int right, int noOfZeros)
{
	if(right == left || right == left + 1) 
	{
		if(getNoOfZeros(left) == noOfZeros)
			return left;
		else if(getNoOfZeros(right) == noOfZeros)
			return right;
		else
			return -1;
	}	
	int mid = (right - left) / 2 + left;
	int noOfZerosMid = getNoOfZeros(mid);
	if(noOfZerosMid < noOfZeros)
		return search(mid, right, noOfZeros);
	else
		return search(left, mid, noOfZeros);
}

int main()
{
	int n;
	freopen("fact.in", "r", stdin);
	freopen("fact.out", "w", stdout);
	
	scanf("%d", &n);
	
	int k = 1;

	while(k < N)
	{
		k *= 5;
		A[length++] = k;
	}

	if(n == 0)
		printf("1");
	else
	{
		printf("%d", search(0, N, n));
	}

	return 0;
}