Cod sursa(job #442825)

Utilizator sunmirrorSorin Stelian sunmirror Data 15 aprilie 2010 14:41:22
Problema Factorial Scor 85
Compilator c Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>

#define IN_FILE "fact.in"
#define OUT_FILE "fact.out"
#define MAX_POWER 12
#define MAX_VALUE 2147483647
#define MIN_VALUE 1

int puteri5[MAX_POWER + 1];

void initializeaza_puteri(void)
{
	int i;

	puteri5[0] = 1;
	for (i = 1; i <= MAX_POWER; i++)
		puteri5[i] = 5 * puteri5[i-1];
}

int cati_de_zero(int N)
{
	int i, num_zero = 0;

	for (i = 1; i < MAX_POWER; i++)
		num_zero+= N/puteri5[i];

	return num_zero;
}

int gaseste_N(int P)
{
	int N, min, max, zerouri, gasit = 0;
	/* Cautare binara pentru un N care "are" P zerouri 
	 * Dupa ce am gasit un astfel de N, e usor sa il gasim pe cel mai mic
	 */
	min = MIN_VALUE;
	max = MAX_VALUE;
	while ((min < max) && (gasit == 0))
	{
		N = min/2 + max/2;
		zerouri = cati_de_zero(N);
		if (zerouri == P)
			gasit = 1;
		else if (zerouri > P)
			max = N - 1;
		else
			min = N + 1;
	}

	if (gasit == 0)
		return -1;
	/* returneaza cel mai mic astfel de N */
	if (N < 5)
		return 1;
	return ((N % 10) > 5) ? (N - (N % 10) + 5) : (N - (N % 10));
}

int main(void)
{
	FILE *fin, *fout;
	int i, N, P;

	fin = fopen(IN_FILE, "r");
	fscanf(fin, "%d", &P);
	fclose(fin);

	initializeaza_puteri();
	N = gaseste_N(P);


	fout = fopen(OUT_FILE, "w");
	fprintf(fout, "%d", N);
	fclose(fout);

	return 0;
}