Cod sursa(job #658121)

Utilizator sausage_catVlad Alin sausage_cat Data 7 ianuarie 2012 22:38:03
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>

const long long cStupidHighNumber = 10000000000;

long GetZeroesFromFactorial(long long x){
	long long counter = 0;
	while(x > 0){
		counter += x = x/5;
	}
	return counter;
}

long long FindFactorialNumberContainingZeroes(int zeroes){
	long long min = 0;
	long long max = cStupidHighNumber;
	long long tempZeroes;
	long long med;
	
	if(zeroes == 0)
		return 1;

	//some binary s#!&@y search
	while(min<max){
		med = (min+max)/2;
		tempZeroes = GetZeroesFromFactorial(med);
		if(tempZeroes == zeroes){
			return med - med%5;
		}
		if(tempZeroes > zeroes){
			max = med;
		}
		if(tempZeroes < zeroes){
			min = med + 1;
		}
	}

	return -1;
}

int main(){
	FILE *fin = fopen("fact.in","r");
	FILE *fout = fopen("fact.out","w");
	int p;
	long n;

	while(!feof(fin)){
		fscanf(fin,"%d", &p);
		fprintf(fout, "%lld\n", FindFactorialNumberContainingZeroes(p));
	}

	return 0;
}