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

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

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

WA in 10061

Post by 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

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 »

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 »

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 »

no problem, my brother in a distant land!

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

Post by srrajesh »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

You can try this case
41 26

Post Reply

Return to “Volume 100 (10000-10099)”