OJ Board

Posted: **Sun Jul 23, 2006 7:34 pm**

shakil wrote:please help me(I am new in acm).

Try the following input:

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

Posted: **Fri Apr 13, 2007 10:20 am**

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

Posted: **Sat Dec 15, 2007 2:58 pm**

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;
}

Posted: **Sat Dec 15, 2007 3:03 pm**

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.

Posted: **Sat Dec 15, 2007 3:46 pm**

how would i do that? any tips? cheers

Posted: **Sat Dec 15, 2007 3:57 pm**

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

Posted: **Sat Dec 15, 2007 4:04 pm**

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

Posted: **Sat Dec 15, 2007 4:45 pm**

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).

scott1991 wrote: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.

Posted: **Sat Dec 15, 2007 5:22 pm**

what does k equal? what does it stand for?

Posted: **Sat Dec 15, 2007 5:28 pm**

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

OJ Board

11038 - How Many O's?

Re: 11038 why wa!!!!!!