lightoj1140

maksyuki 发表于 oj 分类，标签: 组合数学-计数

27 8月 2015

1140 - How Many Zeroes?

InputJimmy writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?

Input starts with an integer T (≤ 11000), denoting the number of test cases.

Each case contains two unsigned 32-bit integers m and n, (m ≤ n).

Output

For each case, print the case number and the number of zeroes written down by Jimmy.

Sample Input

Output for Sample Input

510 11100 2000 500

1234567890 2345678901

0 4294967295

Case 1: 1Case 2: 22Case 3: 92Case 4: 987654304

Case 5: 3825876150

题目类型：组合计数

算法分析：每次从小到大判断N的每一位上的数字，如果当前位上的数字不为0，则该位左边的所有的数字都可以和该位右边的每一位上的数字构成一个合理的结果(每一位上有0~9共10个数)。如果当前位上的数字为0，则该位左边只有小于当前数1的个数可以和右边的right+1个数构成一个合理的结果

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 6000 + 66;

long long Get (long long val)
{
    if (val < 0)
        return 0;

    long long cnt = 1, right = 0, res = 1;
    while (val >= 10)
    {
        long long tt = val % 10;
        val /= 10;
        if (tt)
            res += val * cnt;

        else
            res += (val - 1) * cnt + right + 1;

        right += tt * cnt;
        cnt *= 10;
    }

    return res;
}


int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    long long a, b;
    while (t--)
    {
        cin >> a >> b;

        cout << "Case " << flag++ << ": " << Get (b) - Get (a - 1) << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 6000 + 66;

long long Get (long long val)

{

if (val < 0)

return 0;

long long cnt = 1, right = 0, res = 1;

while (val >= 10)

{

long long tt = val % 10;

val /= 10;

if (tt)

res += val * cnt;

else

res += (val - 1) * cnt + right + 1;

right += tt * cnt;

cnt *= 10;

}

return res;

}

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

long long a, b;

while (t--)

{

cin >> a >> b;

cout << "Case " << flag++ << ": " << Get (b) - Get (a - 1) << endl;

}

return 0;

}

lightoj1131

lightoj1164

超客的水墨烟雨

lightoj1140

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论

2024年12月
一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31