Cod sursa(job #530239)

Utilizator rares192Preda Rares Mihai rares192 Data 7 februarie 2011 11:58:51
Problema Factorial Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 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, 150);
	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)
{
	nr = n / 5;
	
	if( n / 5 > p)
		return -1;
	
	vector<long >::iterator it, sf = putere.end() ;
	
	long long aux;
	rez = 0;
	for( it = putere.begin(); it != sf  && *it <= n; ++it)
	{
		aux = *it;
		while( aux > 1 )
		{
			aux = aux / 5;
			rez++;
		}
		--rez;
	}
	
	if( rez + nr == p)
		return 0;
	if( rez + nr < p)
		return 1;
	else
		return -1;
}