UVA - 1640 The Counting Problem

Observation

This problem gives us two numbers, num1, num2.
Suppose num1 < num2, although might be arbitrary.
Therefore, it’s actually calculate 0 ~ num2 - 0 ~ num1 in every number.

The Problem : Calculate 1 ~ num

To calculate various numbers in 1 ~ num, I use 3 steps. Let b be the maximum that satisfy num / pow(10,b) > 0.

1. calculate 1 ~ pow(10,b)-1, or 1 ~ 999...99, we can recursively solve this by use count_numbers(pow(10,b)-1).
2. calculate the midst of the number, or 10...00 ~ X0...00 - 1, where X is the leading number of num.
3. calculate the back, or X0...00 ~ num

Sample Code

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INF 99999999
#define MAXN 1e8
int base[9] = {0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000};

void solve(vector<int> &res, int num)
{
    if (num == 0)
        return;
    vector<int> v;
    for (int temp = num; temp; temp /= 10)
        v.push_back(temp % 10);
    reverse(v.begin(), v.end());
    int b = v.size() - 1;
    // front : (0 ~ 999...99]
    solve(res, pow(10, b) - 1);

    // middle :  100...0 ~ x00...0 - 1
    for (int j = 0; j < res.size(); j++)
        res[j] += (v[0] - 1) * base[b];
    for (int j = v[0] - 1; j > 0; j--)
        res[j] += pow(10, b);
    // back :  num % pow(10,b)
    // int bNum = num % (int)pow(10,b);
    res[v[0]] += (num % (int)pow(10, b)) + 1;
    for (int i = 1; i < v.size(); i++)
    {
        b--;
        for (int j = 0; j < res.size(); j++)
            res[j] += v[i] * base[b];

        for (int j = 0; j < v[i]; j++)
            res[j] += pow(10, b);
        res[v[i]] += (num % (int)pow(10, b)) + 1;
    }
}

int main()
{
    int num1, num2;
    while (cin >> num1 >> num2 && num1 && num2)
    {
        if (num1 > num2)
            swap(num1, num2);
        vector<int> res1(10, 0);
        vector<int> res2(10, 0);
        solve(res1, num1 - 1);
        solve(res2, num2);
        for (int i = 0; i < res1.size(); i++)
        {
            cout << res2[i] - res1[i];
            if (i != res1.size() - 1)
                cout << " ";
        }
        cout << "\n";
    }
}