11038 - How Many O's?

[Martin Macko]

please help me(I am new in acm).

Try the following input:

Code: Select all

279704366 1037898461
145634828 978264788
146026069 848327284
2034117819 2145545070
1106351446 1941253829
1502186288 1640455732
1096870178 1262485963
1100447501 1763806630
61906328 1355138418
933991114 1164749943
-7 10

My AC's output is:

Code: Select all

648791316
662611986
561424304
153693398
668599232
114207240
139536303
534085361
1135016291
281482563

[shakil]

Thanks Martin Macko for your help. By your help i got AC many time ago.
But forgot to thanks.thanks again.

[scott1991]

HI. I've written the following code for this problem but havn't submitted it yet as it doesn't work even on my machine. I was wondering why it won't work for the large sample inputs and would apreciate any help. Cheers. Scott

Code: Select all

#include <iostream>
#include <math.h>

int main(int argc, char* argv[])
{
	unsigned int n,m,numbof0s=0,length,w;
a:
	scanf("%u%u",&m,&n);
	if(n==-1||m==-1)
		return 0;
	else
	{
		while(m<=n)
		{
			if(m==0)
			{numbof0s+=1;m++;}
		w=m;
		length=int(log10(1.0*w)+1);
		for(length;length>0;length--)
			{
				if(w%10==0)
					{numbof0s++;w=w/10;}
				else
					{w=w/10;}
			}
			m++;
		}
		printf("%u\n",numbof0s);
		numbof0s=0;
		goto a;
	}
	return 0;
}

[mf]

I was wondering why it won't work for the large sample inputs and would apreciate any help

Because it's just too slow. You should do something smarter than iterating over all numbers between m and n, if you want it to run in time.

[scott1991]

how would i do that? any tips? cheers

[mf]

Check out http://www.algorithmist.com/index.php/UVa_11038

[scott1991]

lol...well i didn't understand a word of that(i'm only 16), could you please explane it more simply please? cheers. Scott

[mf]

As an example, let's count zeroes in integers from 1 to 12345. You can do this by separately counting how many times a zero appears in each digit position, and sum these counts.

Let's look at the last position first: a zero appears there in integers 10, 20, 30, ..., 90, 100, 110, ..., 12330, 12340. That's 1234 times in total, which is by the way exactly the first four digits of our number 12345.

Next let's look at the next-to-last digit. All numbers with a zero there are of the form xyz0w, where x,y,z,w are some digits. 1 <= xyz0w <= 12345 if and only if 1 <= xyz <= 123, and 0 <= w <= 9, which means that there are 123 ways to choose the digits xyz, and 10 ways to choose w. The total number of ways to choose xyz and w is product 123*10=1230 -- and this is the number of times a zero appears in the next-to-last digit of all integers between 1 and 12345.

You can go similarly with other digit positions. The formula for (k+1)-st digit from the right is (a prefix of 12345 of length 4-k) * 10^k.

Number of zeros in integers from n to m is the number of zeros in 1..m minus the number of zeros in 1..(n-1).

i'm only 16

You're old enough to understand all this stuff, IMHO.
Belorusian informatics whiz (tourist), IOI's gold medalist, is only 13.

[scott1991]

what does k equal? what does it stand for?

[mf]

Index of digit position from the right: k=0 refers to the last digit, k=1 means next-to-last digit, and so on.