## Baltic OI '13 P2 - Palindrome-Free Numbers

View as PDF

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

Problem type
##### 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 palindrome-free if it does not contain a palindrome with a length greater than as a substring. For example, the number is palindrome-free whereas the number is not because it contains the palindrome .

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

#### Input

The input contains two integers, and .

#### Output

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

#### Constraints

In test cases worth points: .

#### Sample Input 1

123 321

#### Sample Output 1

153

#### Sample Input 2

123456789 987654321

#### Sample Output 2

167386971

• commented on July 18, 2020, 3:11 a.m. edited

How do I avoid a TLE? I'm currently checking numbers one by one to see if they are a palindrome

• commented on July 18, 2020, 5:41 a.m. edit 2

Looping through all the numbers from to is far too slow. A faster approach uses an observation and this technique.