Cod sursa(job #199258)

Utilizator cipPaduraru Ciprian - Ionut cip Data 17 iulie 2008 19:02:46
Problema Factorial Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>

#define MAXD	100000
#define min(a,b) ( a < b ? a : b)

int Numbers[MAXD], n , q ,x ,result;

void cautBin1(int i, int j ,int x)
{
	if (i <= j)
	{
		int mijloc = i + ((j - i)>>1);
		if (Numbers[mijloc] <= x)
		{
			if (Numbers[mijloc] == x)
				result = mijloc;

			cautBin1(mijloc + 1 , j, x);
		}
		else
			cautBin1(i , mijloc - 1, x);
	}
}

void cautBin2(int i, int j, int x)
{
	if (i <= j)
	{
		int mijloc = i + ((j - i)>>1);
		if (Numbers[mijloc] <= x)
		{
			result = mijloc;
			cautBin2(mijloc + 1 , j , x);
		}
		else
			cautBin2(i, mijloc - 1 , x);
	}
}

void cautBin3(int i , int j , int x)
{
	if (i <= j)
	{
		int mijloc = i + ((j - i)>>1);
		if (Numbers[mijloc] < x)
			cautBin3(mijloc + 1, j, x);
		else
		{
			result = mijloc ;
			cautBin3(i, mijloc - 1 , x);
		}
	}
}

int NumberOf0s(int iN)
{
	int S5 = 0 , S2 = 0 , copy = iN;

	while(iN){ S5 += (iN /= 5); }
	while(copy) { S2 += (copy /= 2);}

	return min(S5,S2);
}

int main()
{
	freopen("fact.in","r",stdin);
	freopen("fact.out","w",stdout);

	scanf("%d",&n);

	int l = 0 , r = 100000000 ;
	int result = -1;

	if (n == 0)
		result = 1;
	else
	{
		while ( l <= r )
		{
			int k = l + (( r - l ) >> 1);
			int iNr = NumberOf0s(k);
			if ( iNr >= n )
			{
				if (iNr == n)
					result = k;
				
				r = k - 1 ;
			}
			else 
				l = k + 1;
		}
	}

	printf("%d\n",result);

	return 0;
}