/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は、1 から N までの番号が書かれた N 枚のカードを持っています。この中から、揺れ値がちょうど K であるカードが何枚あるかを知りたいと考えています。
ここで、正の整数の「揺れ値」を次のように定義します。
正の整数を、通常の十進法（先頭に余分な 0 を付けない表記）で表したときの桁数を L とし、最上位桁から順に各桁の数字を d_1, d_2, \ldots, d_L（d_1 \geq 1）とします。このとき、揺れ値は
\sum_{i=1}^{L-1} |d_i - d_{i+1}|
で定義されます。1 桁の数（L = 1）の場合、この和の項は存在しないため揺れ値は 0 です。
例えば、3517 は 4 桁で d_1 = 3, d_2 = 5, d_3 = 1, d_4 = 7 なので、揺れ値は |3-5| + |5-1| + |1-7| = 2 + 4 + 6 = 12 です。また、7 は 1 桁なので揺れ値は 0 です。
1 以上 N 以下の整数のうち、揺れ値がちょうど K であるものの個数を求めてください。
制約
- 1 \leq N \leq 10^{18}
- 0 \leq K \leq 153
- N および K は整数である
入力
N K
カードの枚数を表す整数 N と、目標とする揺れ値を表す整数 K が、スペース区切りで 1 行で与えられる。
出力
1 以上 N 以下の整数のうち、揺れ値がちょうど K であるものの個数を 1 行で出力せよ。
入力例 1
20 1
出力例 1
2
入力例 2
100 0
出力例 2
18
入力例 3
1234567 12
出力例 3
73745
入力例 4
987654321012345678 80
出力例 4
3107339199338170
入力例 5
1 0
出力例 5
1
Score : 433 pts
Problem Statement
Takahashi has N cards numbered from 1 to N. He wants to know how many of these cards have a fluctuation value of exactly K.
Here, the "fluctuation value" of a positive integer is defined as follows:
Let L be the number of digits when a positive integer is represented in standard decimal notation (without leading zeros), and let the digits from the most significant to the least significant be d_1, d_2, \ldots, d_L (d_1 \geq 1). The fluctuation value is defined as:
\sum_{i=1}^{L-1} |d_i - d_{i+1}|
For a single-digit number (L = 1), there are no terms in this sum, so the fluctuation value is 0.
For example, 3517 has 4 digits with d_1 = 3, d_2 = 5, d_3 = 1, d_4 = 7, so its fluctuation value is |3-5| + |5-1| + |1-7| = 2 + 4 + 6 = 12. Also, 7 is a single-digit number, so its fluctuation value is 0.
Find the number of integers between 1 and N, inclusive, whose fluctuation value is exactly K.
Constraints
- 1 \leq N \leq 10^{18}
- 0 \leq K \leq 153
- N and K are integers.
Input
N K
The integer N representing the number of cards and the integer K representing the target fluctuation value are given in a single line, separated by a space.
Output
Print the number of integers between 1 and N, inclusive, whose fluctuation value is exactly K in a single line.
Sample Input 1
20 1
Sample Output 1
2
Sample Input 2
100 0
Sample Output 2
18
Sample Input 3
1234567 12
Sample Output 3
73745
Sample Input 4
987654321012345678 80
Sample Output 4
3107339199338170
Sample Input 5
1 0
Sample Output 5
1