New Year's '18 P4 - The Polar Express

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Mimi has just won two raffle tickets for the Polar Express! Unfortunately, there is just one obstacle in the way — the skill testing question!

Let us define \operatorname S(x) to be the sum of digits of x. Given two positive integers, L and R, compute the number of distinct values of \operatorname S(x), for x = L, L+1, \dots, R.

Mimi has agreed to give you the other ticket if you help her solve this problem. Can you do it?


Subtask 1 [10%]

1 \le L \le R \le 10^5

Subtask 2 [90%]

1 \le L \le R \le 10^{18}

Input Specification

The first and only line of input will contain two space separated integers, L and R.

Output Specification

A single integer, the number of distinct values of \operatorname S(x).

Sample Input

19 28

Sample Output



There are no comments at the moment.