Baltic OI '13 P2 - Palindrome-Free Numbers

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 128M

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
Baltic Olympiad in Informatics: 2013 Day 1, Problem 2

A string is a palindrome if it remains the same when it is read backwards. A number is palindromefree if it does not contain a palindrome with a length greater than 1 as a substring. For example, the number 16\,276 is palindrome-free whereas the number 17\,276 is not because it contains the palindrome 727.

Your task is to calculate the total number of palindrome-free numbers in a given range.

Input

The input contains two integers, a and b.

Output

The output should contain one integer: the total number of palindrome-free numbers in the range a, \dots, b (including a and b).

Constraints

0 \le a \le b \le 10^{18}

In test cases worth 25 points: b-a \le 100\,000.

Sample Input 1

123 321

Sample Output 1

153

Sample Input 2

123456789 987654321

Sample Output 2

167386971

Comments

There are no comments at the moment.