Cod sursa(job #1024772)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 9 noiembrie 2013 00:45:29
Problema Factorial Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<iostream>
#include<stdio.h>
#define Nmax 100000000
using namespace std;


int P;

bool check(int x, int p)
{
	int mid = x;
	int nr5 = 0;

    for(int putere5 = 5; mid / putere5; putere5 *= 5)
            nr5 += mid / putere5;
	if(nr5 == p)
		return true;
	return false;
}


int main()
{
	int upper_bound = 100000000;
	int lower_bound = 0;
	int sol = 100000001;
	int sol1, sol2;
    freopen("fact.in","r", stdin);
    freopen("fact.out", "w", stdout);
 
    cin >> P;
	if(P == 0)
	{
		cout << '1' << endl;
		return 0;
	}

	while(lower_bound < upper_bound)
	{
		int nr5 = 0, putere5 = 5;
		int mid = ( lower_bound + upper_bound ) / 2;

		for(int putere5 = 5; mid / putere5; putere5 *= 5)
            nr5 += mid / putere5;

		if(nr5 == P)
		{
			if(mid < sol)
				sol = mid;
			sol1 = sol;
			sol2 = sol;
			while(sol1 % 5 != 0)
				sol1--;
			while(sol2 % 5 != 0)
				sol2++;
			if(check(sol1, P) == true)
			{
				sol = sol1;
				break;
			}
			if(check(sol2, P) == true)
			{
				sol = sol2;
				break;
			}
		}

		if(nr5 < P)
		{
			lower_bound = mid + 1;
		}
		else
		{
			upper_bound = mid - 1;
		}
	}
	cout << sol << endl;
    return 0;
}