10061 - How many zero's and how many digits ?

[Sedefcho]

To nymo: thanks a lot from me.
I started attacking this problem today and
your post was crucial for solving it. After
about 15 submissions I got ACC.

Here is some more input from me for anyone who
might still be trying to solve it.
Note: 1048575 = 2^20 - 1, this according to the
problem statement is the largest number allowed
in the input as a value for N.

INPUT

Code: Select all

0 2
1 2
2 9 
100 23 
23 101 
23233 344 
34 799 
1000000 799
1000010 800
1048575 2
1048575 3
1048575 17
1048575 101
1048575 799
1048575 800

OUTPUT

Code: Select all

0 1
0 1
0 1
4 117
0 12
552 36014
0 14
21737 1917527
125000 1917188
1048555 19458736
524281 12277096
65533 4760591
10484 2922517
22794 2018112
131070 2017734

Good luck to everyone!

[shihabrc]

Getting WA in this prob. My code passed all the inputs posted in the prev posts. I still don't know my fault. I'm giving my code.

Code: Select all

Cut after AC

[yiuyuho]

change
digit=floor(logarithm/log10(base))+1;
to
digit=floor(logarithm/log10(base)+1e-9)+1;

Yes, watch them floats!

[shihabrc]

Thanx. Got AC NOW. .

[yiuyuho]

no problem, my brother in a distant land!

[srrajesh]

dear Antonio Ocampo,
For number of digits, i did the following:

Code: Select all

for(sum=0.0,i=1;i<=n;++i) // change in indexing
          sum+=(log10(i)/log10(b)); // change

         // cout<<ceros(n,b)<<" "<<int(floor(sum/log10(b)))+1<<"\n";
         cout<<ceros(n, b)<<" ";
         if (sum - floor(sum) < 1e-14)
         	sum ++;
         else
         	sum = floor(sum + 1);

         printf("%.0lf\n", sum);
      }

Indeed, this helped me a lot!
Though, my code works with all the test case in this forum, I think there should be some sort of rounding off error, which produced WA!
When I added checking with "epsilon" 1e-14, as in your code, I got AC.
Thanks a lot.

But I am curious to know, what test case necessiates such a checking.
The test cases given in this thread don't need such a checking!
I really want to see such a test case, because I suffered a lot of WAs owing to that!

[rhsumon]

Where is the problem i cannot find
plz help some one
here is my code:

Code: Select all

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define P 2005
#define M 1050000

long prime[P]; 
long p[500];
double f[500]; 

void gen_prime(){
	int i,j;
	prime[0] = prime[1] = 1;
	for(i=2; i<=(long)sqrt(P); i++){
		if(prime[i]==0){ 
			for(j=i*i; j<=P-1; j=j+i){
				prime[j]=1;
			}
		}
	} 
	j=0; 
	for(i=0; i<=P-1; i++){ 
		if(prime[i] == 0){
			p[j] = i;
			f[j++]=0;
		}
	}
}

double tzero(int n,int b){
	int i=0,j,nn;
	while(b!=1){
		while(b%p[i]==0){
			f[i]++;
			b/=p[i];
		}
		i++;
	}
	double sum,min=M;
	for(j=0; j<i; j++){
		nn=n;
		sum=0;
		if(f[j]!=0){
			while(nn!=0){
				sum+=nn/p[j];
				nn/=p[j];
			}
			if(min > sum/f[j])
				min=sum/f[j];
			f[j]=0;
		}
	}
	return floor(min);
		
}

double tdigit(int n,int b){
	double sum;
	int i;
	if(n==0) return 1;
	else{
		sum=0;
		for(i=1;i<=n;i++){
			sum+=log10(i)/log10(b);
		}
		return floor(sum)+1;
	}	
}

int main()
{
	freopen("10061.out","w", stdout);
	gen_prime();
	double zcount,dcount;
	int n,b;
	while(scanf("%d%d",&n,&b)==2){
		zcount=tzero(n,b);
		dcount=tdigit(n,b);
		printf("%.0f %.0f\n",zcount,dcount);
	}
	return 0;
}

Plz take a look anybody.......... :cry: 

[amishera]

I read the above posts and tested all the inputs and also changed some modifications suggested in prior posts. The outputs seem to agree on the answers provided but the same wrong answer.

Code: Select all

#include <stdio.h>
#include <math.h>

#define MAX_LONG 2147483647

int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547,
557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797};

int maxPower(int n, int p)
{
	int power = p;
	int mp = 0;
	int tn = n;
	while (tn % power == 0)
	{
		mp++;
		power *= p;
	}
	return mp;
}

unsigned long maxFactorialPower(unsigned long n, int p)
{
	unsigned long power = p;
	unsigned long sum = 0;
	while (n >= power)
	{
		sum += n/power;
		power *= p;
	}
	return sum;
}


int main()
{
	unsigned long n;
	int b,i, mp;
	double pi=2*acos(double(0.0));
	double e=exp(double(1.0));

	unsigned long mfp;
	while (scanf("%lu %d",&n,&b) != EOF)
	{
		unsigned long nDigit, nZero = MAX_LONG;
		for (i = 0;i < 139;i++)
		{
			if (b < primes[i])
				break;
			if (b % primes[i] == 0)
			{
				mp = maxPower(b,primes[i]);
				mfp = maxFactorialPower(n,primes[i]);
				unsigned long tnd = mfp/mp;
				if (tnd < nZero)
					nZero = tnd;
			}
		}
		double num = 0;

		/*for (i = 1;i <= n;i++)
		{
			num += log(i);
		}

		double denom = log(b);*/
		if (n == 0 || n == 1)
		{
			printf("0 1\n");
		}
		else {
			nDigit = floor((log(2*pi*n)/2+n*log(n/e))/log(double(b))+0.000001)+1;
			printf("%lu %lu\n",nZero,nDigit);
		}
	}
	return 0;
}

Some suggestion please.

[SeregiB]

Hi!

Any idea, what is wrong with this code?

Code: Select all

#include <stdio.h>
#include <limits.h>
#include <math.h>
#include <stdlib.h>
unsigned int digits(unsigned int n, unsigned int base)
{
  return (unsigned int)(floor((log10(2*M_PI*n)/2+n*(log10(n)-log10(M_E)))/log10(base)+1e-9)+1);
}
unsigned int legendre(int n, int p)
{
	long long int i, log_p_n = (int)(log10(n) / log10(p)), summa = 0;
	for(i = 1; i <= log_p_n; i++)
	{
		summa += (long long int)floor(n/pow(p,i));
	}
	return summa;
}
unsigned int zeros(unsigned int k, unsigned int num)
{
  unsigned int * exp;
  unsigned int t[34] = {0}, min = LONG_MAX;
  exp = (unsigned int*)malloc(1048600);
  unsigned int i = 0, c = 0, d = 2, j;
  while(k > 1)
	{
    if(k % d == 0)
		{
      k /= d;
			if(t[i-1] != d)
			{
      	t[i] = d;
      	i++;
			}
			exp[d]++;
    }
    else d++;
  }
  for(j = 0; j < i; j++)
	{
		k = legendre(num,t[j]) / exp[t[j]];
		if(k < min) min = k;
  }
  return min;
}
unsigned int n = 0, base, z;
int main()
{
	while(scanf("%d %d",&n,&base) != EOF)
	{
		z = digits(n,base);
		if(!z) z = 1;
		printf("%d %d\n",zeros(base,n),z);
	}
  return 0;
}

I have tried out with many test cases and I got right results, so I do not understand what is the problem.

[Ahmad]

there is a very simple Algorithm to get the number of zeros without making any prime factoring ...
All what we have to do is finding how many times the base divides the factorial ... we can do it in O(n) but we will have to avoid the overflow ...
that's where the modulus part comes ... and i will let you think about this number (the Mod)
Hint : (think about finding the last nonzero digit in decimal for a factorial)

[magurmach]

Getting WA in this problem...

PLZ PLZ Help!

Code Link: Code removed after AC


Thanks in advance!

[brianfry713]

It looks like you figured it out.

[magurmach]

If getting WA then most possibly the cause is precision
The problem is in digit calculation. Problem is not in formula but precision. add 1e-9 before converting double to long or the format used! Many problems will be solved!

[ryx]

You can try this case
41 26