UVa 11038

Summary

Write down all integers between $m$ and $n$ inclusive ($m\leq n$ ) in decimal. How many 0's will you write?

Explanation

Notation: ${\overline {a_{n}a_{n-1}\dots a_{0}}}$ denotes an integer $a=a_{n}10^{n}+a_{n-1}10^{n-1}+\cdots +a_{0}$ . That is $a_{n},\ a_{n-1},\ \dots ,\ a_{0}$ are the decimal digits of $a$ , from left to right.

Let's solve an easier problem. How many 0's are there in numbers between 0 and $b$ inclusive? If we denote this number by $f(b)$ then the answer to our original problem is just $f(n)-f(m-1)$ .

Let $b={\overline {b_{n}b_{n-1}\dots b_{0}}}$ . Let's find for each position $0\leq k how many times a zero appears there as we are counting from 0 to $b$ .

If $b_{k}>0$ , then by setting $a_{k}=0$ , and choosing the other digits according to the constraints: $1\leq {\overline {a_{n}\dots a_{k+1}}}\leq {\overline {b_{n}\dots b_{k+1}}}$ , and $0\leq {\overline {a_{k-1}\dots a_{0}}}<10^{k}$ , we will have a positive integer $a={\overline {a_{n}\dots a_{0}}}$ , which is not greater than $b$ , and the $k$ -th digit of which exists and is equal to zero. There are $10^{k}\cdot {\overline {b_{n}\dots b_{k+1}}}$ such integers.

If $b_{k}=0$ , same analysis as above applies, except that when ${\overline {a_{n}\dots a_{k+1}}}={\overline {b_{n}\dots b_{k+1}}}$ there are only $1+{\overline {b_{k-1}\dots b_{0}}}$ ways to choose the digits to the right of $a_{k}$ . So in this case there are $(10^{k})\cdot ({\overline {b_{n}\dots b_{k+1}}}-1)+1+{\overline {b_{k-1}\dots b_{0}}}$ integers between 0 and $b$ , in which the $k$ -th digit is zero.

The total number of zeroes is the sum of the number of times a zero occurs in each position, plus 1 for the integer "0".

Input

10 11
100 200
0 500
1234567890 2345678901
0 4294967295
1001010101 1010101010
3020203 302010203
-1 -1

1
22
92
987654304
3825876150
23709830
231396207