Cod sursa(job #530306)

Utilizator rares192Preda Rares Mihai rares192 Data 7 februarie 2011 15:01:01
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
#include<vector>
using namespace std;

#define INF 1000000000000000000LL
ofstream fout("fact.out");

void read();
int ok(long long);
void cauta(long long st, long long dr);
void solve();

vector<long > putere;

int p;
long long nr;
int rez = 0;

int main()
{
	read();
	solve();
	cauta(1, INF);
	fout.close();
	return 0;
}

void read()
{
	ifstream fin("fact.in");
	fin >> p;
	
	fin.close();
}

void solve()
{
	if( p == 0 )
	{
		fout << 1;
		exit(0);
	}
	
	long long put = 1;
	while( 5 * put <= INF)
	{
		put = 5 * put;
		putere.push_back(put);
	}
}

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

int ok(long long n)
{
	long long nr = n / 5;
	if( nr > p)
		return -1;
		
	long long c = 0;
	while( (long long)(n / 5) > 0)
	{
		n = n / 5;
		c += n;
	}
	
	if( c == p)
		return 0;
	if( c < p)
		return 1;
	else
		return -1;
}