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

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Aug 01, 2006 11:59 pm

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
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

WA in 10061

Post by shihabrc » Tue Aug 22, 2006 9:30 pm

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

Last edited by shihabrc on Wed Aug 23, 2006 4:01 pm, edited 1 time in total.
Shihab
CSE,BUET

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Tue Aug 22, 2006 10:27 pm

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

Yes, watch them floats!

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

Post by shihabrc » Wed Aug 23, 2006 3:59 pm

Thanx. Got AC NOW. :D.
Shihab
CSE,BUET

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Wed Aug 23, 2006 9:42 pm

no problem, my brother in a distant land!

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

Post by srrajesh » Tue Dec 04, 2007 9:43 pm

nymo wrote: 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
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

Re: 10061 - How Many Zeros and How Many Digits?

Post by rhsumon » Sun Aug 17, 2008 12:39 pm

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
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

Re: 10061 - How Many Zeros and How Many Digits?

Post by amishera » Wed Dec 31, 2008 11:56 pm

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
New poster
Posts: 3
Joined: Wed Aug 06, 2008 9:24 pm
Location: Hungary, Debrecen
Contact:

Re: 10061 - How Many Zeros and How Many Digits?

Post by SeregiB » Sun Dec 20, 2009 12:45 pm

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.
Sorry for my poor english :-)

Ahmad
New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

Re: 10061 - How Many Zeros and How Many Digits?

Post by Ahmad » Sat Sep 10, 2011 4:37 pm

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
New poster
Posts: 26
Joined: Mon May 14, 2012 8:19 pm

Re: 10061 - How Many Zeros and How Many Digits?

Post by magurmach » Sun May 27, 2012 3:15 pm

Getting WA in this problem...

PLZ PLZ Help!

Code Link: Code removed after AC


Thanks in advance!
Last edited by magurmach on Mon Jun 11, 2012 10:21 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10061 - How Many Zeros and How Many Digits?

Post by brianfry713 » Fri Jun 01, 2012 1:17 am

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

magurmach
New poster
Posts: 26
Joined: Mon May 14, 2012 8:19 pm

Re: 10061 - How Many Zeros and How Many Digits?

Post by magurmach » Mon Jun 11, 2012 10:24 am

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
New poster
Posts: 4
Joined: Fri Jul 10, 2015 2:52 am

A hard test case

Post by ryx » Fri Jul 10, 2015 3:01 am

You can try this case
41 26

Post Reply

Return to “Volume 100 (10000-10099)”