Cod sursa(job #363707)

Utilizator eukristianCristian L. eukristian Data 14 noiembrie 2009 12:09:29
Problema Factorial Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
using namespace std;

int f(int n);
int BinarySearch(int *array, int key, int low, int high);
int bin(int p , int a , int b);
 
int main()
{
	ifstream fin("fact.in");
	ofstream fout("fact.out");
	int P;fin >> P;
	fout << bin(P,0,1000000);
	return 0;
}

int BinarySearch(int *array, int key, int low, int high)
{
  int middle;
  if(low > high)
    return -1;
  middle = (low+high)/2;
  if(array[middle] == key)
    return middle;
  else if(array[middle] > key)
    return BinarySearch(array, key, low, middle-1); 
    return BinarySearch(array, key, middle+1, high);
}

int bin(int p , int a , int b)
{
	int mid = (a+b)/2;
	if (a > b)
	{
		return -1;
	}
	int value = f(mid);
	if(value == p)
	{
		return (mid - (mid % 5));
	}
	else if(value < p)
	{
		return bin(p,mid + 1 , b);
	}
	else
	{
		return bin(p,a,mid - 1);
	}
}

int f(int n)
{
	int p = 0;
	for (int i = 5 ; i <= n; i += 5)
	{
		int x = i;
		while (!(x % 5))
		{
			p++;
			x /= 5;
		}
	}
	return p;
}