Cod sursa(job #1721496)

Utilizator elena.marinicaMarinica Elena-Georgiana elena.marinica Data 25 iunie 2016 19:29:36
Problema Factorial Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#include <iostream>
#include <vector>

std::vector<int> v;

int power_of_5(int x, int p) {
	//x / 5 ^ p
	int p5 = 1;
	for(int  i = 1; i <= p ; ++i)
		p5 *= 5;
	return x / p5;
}

int zeros(int x) {
	
	int cnt = 1;
	int res = 0;
	int sum = 0;
	while( ( res = power_of_5(x, cnt) ) != 0 ) {
		sum += res;
		cnt++;
	}	
	return sum;
}

int binary_search( int P) {
	
	int pos ; int step;
	
	for(step = 1; step <= P * 5 ; step *= 2);
	
	for(pos = 0; step > 0; step /= 2)
		if(pos + step <= P * 5 && zeros(pos + step) < P)
			pos += step;
			
	return pos + 1;
}


int main() {
	
	int P;
	FILE *fin = fopen("fact.in", "r");
	FILE *fout = fopen("fact.out", "w");
	
	fscanf(fin, "%d", &P);
	
	for (int i = 0; i < P * 5; i++) {
		v.push_back(i);	
	}
	
	int res = binary_search( P);
	
	fprintf(fout, "%d\n", res);
	
	fclose(fin);
	fclose(fout);
}