সবাইকে বসন্তের বাতাসে ভেসে ভেড়ান ফুলের কলির শুভেচ্ছা দিয়ে আমরা এক নতুন সমস্যার সমাধান করতে যাচ্ছি ।
Problem Statement :
Jimmy writes down the decimal representations of all natural numbers between and including a and b, (a ≤ b). How many zeroes will he write down?

Example :
Suppopse Jimmy write 10 and 15 as in following order .

10 11 12 13 14 15

In the above number there are total 1 zeroes . So you have to output 1 .

Solution Idea :

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

2. Let's solve an easier problem.
-------- How many 0's are there in numbers between 0 and

b

inclusive?

3. If we denote this number by

f (b)

then the answer to our original problem is just

f (n) - f (m - 1)

.

4. Let $b = \overline{b_n b_{n-1} \dots b_0}$ .

5. Let's find for each position $0 \le k < n$ how many times a zero appears there as we are counting from 0 to

b

.

6. If

b k > 0

, then by setting

a k = 0

, and choosing the other digits according to the constraints: $1 \le \overline{a_n \dots a_{k+1}} \le \overline{b_n \dots b_{k+1}}$ , and $0 \le \overline{a_{k-1} \dots a_0} < 10^k$ ,

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

8. There are $10^k \cdot \overline{b_n \dots b_{k+1}}$ such integers.

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

.

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

11. 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".

Solution Code :

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

long long int count_zeroes(long long int b)
{
if (b < 0) return 0;

// Compute decimal representation of b
char s[20];
sprintf(s, "%lld", b);
int n = strlen(s);

// Compute powers of 10
long long ten[20] = { 1 };
for (int n = 1; n < 20; n++)
ten[n] = ten[n-1] * 10;

// Compute suffixes of b.suf[k] = atoll(s+k).
long long suf[20];
suf[n] = 0;
for (int i = n-1; i >= 0; i--)
suf[i] = suf[i+1] + (s[i] - '0') * ten[n-i-1];

long long res = 1, pref = 0;
for (int k = 1; k < n; k++) {
pref = pref * 10 + (s[k-1] - '0');
// pref is equal to integer, formed by first k digits of b.

if (s[k] != '0')
res += pref * ten[n-k-1];
else
res += (pref - 1) * ten[n-k-1] + suf[k+1] + 1;
}
return res;
}

int main()
{
int i,test;
long long m,n;
cin>>test;
for(int i=1;i<=test;i++)
{
cin>>m>>n;
printf("Case %d: %lld\n",i,count_zeroes(max(m,n))-count_zeroes(min(m,n)-1));
}
return 0;
}

Solution For LightOJ

বুধবার, ২০ ফেব্রুয়ারী, ২০১৩

Solution of Light OJ 1140 - How Many Zeroes?

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন