Description

windy 定义了一种 windy 数. 不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数. windy 想知道, 在 A 和 B 之间, 包括 A 和 B, 总共有多少个 windy 数?

Input

包含两个整数,\(A, B\).

Output

一个整数.

Sample Input

25 50

Sample Output

20

Data Range

100% 的数据, 满足 \(1 \leq A \leq B \leq 2 \times 10^9\).

Explanation

数位 DP, 考虑一共有几位时所有以某个数字开头的数字 (以内) 一共有多少个 windy 数. 这样的话就可以记:

\[dp[i][j]\]

具体转移方程可以看代码.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;
typedef long long int lli;
const int maxn = 20;

lli A, B;
lli pow_10[maxn];
lli dp[maxn][10];

int eval(lli n)
{
    if (n <= 0)
        return 0;
    lli res = 0; // Final result
    int n_dig = 10; // Digits of n, in base-10
    // Retrieving digits of n
    while (pow_10[n_dig] > n)
        n_dig--;
    // Adding large blobs of data.
    // Take n = 512 for example.
    // res += dp[0-9], dp[00-99]
    for (int i = 1; i <= n_dig; i++)
        for (int j = 1; j <= 9; j++)
            res += dp[i][j];
    // Take n = 512 for example.
    // The following steps will execute the following operations:
    // res += dp[100-199], dp[200-299], ..., dp[400-499].
    int cur_dig = n / pow_10[n_dig];
    for (int i = 1; i < cur_dig; i++)
        res += dp[n_dig + 1][i];
    n %= pow_10[n_dig];
    // Processing all data beginning from:
    // If n = 12, res += dp[500-512].
    int last_dig = cur_dig;
    for (int i = n_dig + 1 - 1; i >= 1; i--) {
        cur_dig = n / pow_10[i - 1];
        if (i == 1) {
            for (int j = 0; j <= cur_dig; j++)
                if (abs(last_dig - j) >= 2)
                    res += dp[i][j];
        } else {
            for (int j = 0; j < cur_dig; j++)
                if (abs(last_dig - j) >= 2)
                    res += dp[i][j];
        }
        if (abs(last_dig - cur_dig) < 2)
            break;
        last_dig = cur_dig;
        n %= pow_10[i - 1];
    }
    return res;
}

int main(int argc, char** argv)
{
    scanf("%lld%lld", &A, &B);
    // Pre-building dynamic programming array.
    pow_10[0] = 1;
    for (int i = 1; i <= 10; i++)
        pow_10[i] = pow_10[i - 1] * 10;
    // First digit, datum from 0 through 9
    for (int j = 0; j <= 9; j++)
        dp[1][j] = 1;
    // Digits' count, from 2 through 10
    for (int i = 2; i <= 10; i++)
        // Current digit (i-th)
        for (int j = 0; j <= 9; j++)
            // Previous digit ((i-1)-th)
            for (int k = 0; k <= 9; k++)
                if (abs(j - k) >= 2)
                    dp[i][j] += dp[i - 1][k];
    // Finished initial DP procedure.
    // Collecting data.
    lli res = eval(B) - eval(A - 1);
    printf("%lld\n", res);
    return 0;
}