/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は、整数の各桁のバランスを調べることに興味を持っています。
正の整数を、先頭にゼロをつけない通常の十進表記で表したとき、その桁数を k とし、各桁の数字を左（最上位）から順に d_1, d_2, \ldots, d_k とします（d_1 \geq 1）。このとき、左から数えて奇数番目（1 番目、3 番目、5 番目、…）の桁の数字の合計を S_{\mathrm{odd}} = d_1 + d_3 + d_5 + \cdots、偶数番目（2 番目、4 番目、6 番目、…）の桁の数字の合計を S_{\mathrm{even}} = d_2 + d_4 + d_6 + \cdots とします。該当する桁が存在しない場合（和をとる項が 0 個の場合）、その合計は 0 とします。たとえば、1 桁の正の整数では偶数番目の桁が存在しないため S_{\mathrm{even}} = 0 です。
正の整数 N と非負整数 D が与えられます。正の整数が バランスが良い とは、
|S_{\mathrm{odd}} - S_{\mathrm{even}}| \leq D
を満たすこと、すなわち、奇数番目の桁の数字の合計と偶数番目の桁の数字の合計の差の絶対値が D 以下であることを言います。
たとえば D = 2 のとき、整数 31415 について考えます。奇数番目の桁の数字は d_1 = 3, d_3 = 4, d_5 = 5 で S_{\mathrm{odd}} = 12、偶数番目の桁の数字は d_2 = 1, d_4 = 1 で S_{\mathrm{even}} = 2 です。差の絶対値は |12 - 2| = 10 であり D = 2 を超えるため、この整数はバランスが良くありません。一方、整数 123 では S_{\mathrm{odd}} = 1 + 3 = 4、S_{\mathrm{even}} = 2 で差の絶対値は 2 であり D = 2 以下なので、バランスが良い整数です。
1 以上 N 以下の正の整数のうち、バランスが良いものの個数を求めてください。
制約
- 1 \leq N \leq 10^{15}
- 0 \leq D \leq 100
- N は整数である
- D は整数である
入力
N D
- 1 行目には、整数の上限を表す正の整数 N が与えられる。
- 2 行目には、バランスの判定に用いる許容差を表す非負整数 D が与えられる。
出力
1 以上 N 以下の正の整数のうち、バランスが良いものの個数を 1 行で出力せよ。
入力例 1
123 2
出力例 1
52
入力例 2
50 0
出力例 2
4
入力例 3
100000 5
出力例 3
49917
入力例 4
987654321012345 20
出力例 4
901100492234266
入力例 5
1 0
出力例 5
0
Score : 433 pts
Problem Statement
Takahashi is interested in examining the balance of the digits of integers.
When a positive integer is written in its standard decimal representation without leading zeros, let k be its number of digits, and let d_1, d_2, \ldots, d_k be its digits from left (most significant) to right (d_1 \geq 1). Define the sum of digits at odd-numbered positions (1st, 3rd, 5th, …) counting from the left as S_{\mathrm{odd}} = d_1 + d_3 + d_5 + \cdots, and the sum of digits at even-numbered positions (2nd, 4th, 6th, …) as S_{\mathrm{even}} = d_2 + d_4 + d_6 + \cdots. If no such positions exist (i.e., the sum has 0 terms), the sum is defined as 0. For example, for a single-digit positive integer, there are no even-numbered positions, so S_{\mathrm{even}} = 0.
Given a positive integer N and a non-negative integer D, a positive integer is said to be well-balanced if it satisfies
|S_{\mathrm{odd}} - S_{\mathrm{even}}| \leq D
That is, the absolute value of the difference between the sum of digits at odd-numbered positions and the sum of digits at even-numbered positions is at most D.
For example, when D = 2, consider the integer 31415. The digits at odd-numbered positions are d_1 = 3, d_3 = 4, d_5 = 5, giving S_{\mathrm{odd}} = 12, and the digits at even-numbered positions are d_2 = 1, d_4 = 1, giving S_{\mathrm{even}} = 2. The absolute value of the difference is |12 - 2| = 10, which exceeds D = 2, so this integer is not well-balanced. On the other hand, for the integer 123, S_{\mathrm{odd}} = 1 + 3 = 4, S_{\mathrm{even}} = 2, and the absolute value of the difference is 2, which is at most D = 2, so it is a well-balanced integer.
Find the number of positive integers between 1 and N, inclusive, that are well-balanced.
Constraints
- 1 \leq N \leq 10^{15}
- 0 \leq D \leq 100
- N is an integer
- D is an integer
Input
N D
- The first line contains a positive integer N, representing the upper limit of the integers.
- The second line contains a non-negative integer D, representing the tolerance used for the balance check.
Output
Output in one line the number of positive integers between 1 and N, inclusive, that are well-balanced.
Sample Input 1
123 2
Sample Output 1
52
Sample Input 2
50 0
Sample Output 2
4
Sample Input 3
100000 5
Sample Output 3
49917
Sample Input 4
987654321012345 20
Sample Output 4
901100492234266
Sample Input 5
1 0
Sample Output 5
0