The Polar Express

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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, \ldots R-1,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.