Cod sursa(job #530240)

Utilizator david_raucaRauca Ioan David david_rauca Data 7 februarie 2011 11:59:28
Problema Factorial Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<fstream>
#include<vector>
using namespace std;

#define INF 1000000000000000000LL

ifstream fin("fact.in");
ofstream fout("fact.out");

long long p;

vector<long long> v;

void Solve();
void Search(long long st, long long dr );
int OK( long long n);

int main()
{
	fin >> p;
	
	Solve();
	Search(1, INF);
	
	fin.close();
	fout.close();
	
	return 0;
}

void Solve()
{
	if( p == 0 )
	{
		fout << 1;
		return;
	}
	
	long put = 1;
	
	while( 5 * put <= INF )
	{
		put = 5 * put;
		v.push_back(put);
	}
}

void Search(long long st, long long dr )
{
	if( st >= dr )
	{
		fout << -1;
		exit(0);
	}
	long long mij = (st+dr)/2;
	
	long long rasp = OK(mij);
	
	if( rasp == 0 )
	{
		fout << mij;
		exit(0);
	}
	else
	{
		if( rasp == 1)
			Search(mij+1, dr);
		else
			Search(st, mij);	
	}
}

int OK( long long n )
{
	long long nr;
	nr = n / 5;
	
	long long rez = 0;
	for( int i = 0; i <= n; ++i )
	{
		long long x = v[i];
		while( x > 1 )
		{
			x = x / 5;
			rez++;
		}
		rez--;
	}
	
	if( rez + n == p )
		return 0;
	if( rez + n < p )
		return 1;
	else
		return -1;
}