Cod sursa(job #488965)

Utilizator g3ppyStoian Vlad g3ppy Data 30 septembrie 2010 17:26:01
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>
#define uint unsigned long long
#define N 400000020

using namespace std;

inline uint nrz( uint n )
{
	uint count = 0;
	uint d,r;
	d = r = 1;
	while (r > 0)
	{
		d *= 5;
		r = n/d; // [x] is greatest integer less than x
		count += r;
	}
	
	return count;
}


uint binary_search(uint val)
{
    uint i, step;
    for (step = 1; step < N; step <<= 1);
	
    for (i = 0; step; step >>= 1)
        if (i + step < N && nrz(i + step) <= val)
           i += step;
    return i;
}


int main()
{
	ifstream fin("fact.in");
	ofstream fout("fact.out");
	
	uint p, pos;
	
	fin >> p;
	
	if ( p == 0 )
	{
		fout << 1;
		return 0;
	}
	
	pos = binary_search( p );
	
	if ( (pos % 10) < 5 ) pos = (pos/10) * 10;
	else pos = (pos/10) * 10 + 5;
	
	if ( nrz( pos ) == p ) fout << pos;
	else fout << -1;
	
	fin.close();
	fout.close();	
	return 0;
}