TLE '17 Contest 8 P3 - Curious Numbers

View as PDF

Submit solution

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

Problem type
Fax McClad is a deep thinker.

Fax McClad, Croneria's most curious bounty hunter, is interested certain numbers.

A number is called a palindrome if it is the same when read left-to-right or right-to-left. For example, 12\,321 is a palindrome, and 1\,234 is not. Leading zeroes are not part of a palindrome. For example, 3\,130 is not a palindrome.

Fax also loves the number K and any multiple of it.

Fax is interested in the palindromes that are divisible by K between M and N, inclusive. He will do this Q times. Can you tell him how many of these numbers there are?

Input Specification

The first line of input will contain Q (1 \le Q \le 10^5) and K (1 \le K \le 10^{10}).

The Q lines of input follow. Each line will contain M and N (1 \le M \le N \le 10^{10}).

For 20\% of the points, N,M,K,Q \le 10^3.

For an additional 30\% of the points, N,M,K \le 10^6, Q \le 10^3.

Output Specification

On separate lines, print the answer to each query.

Sample Input

2 2
10 50
100 300

Sample Output


Explanation for Sample Output

For the first query, 11, 22, 33, 44 are the only palindromes in between 10 and 50. Only 22 and 44 are divisible by 2.


  • 1
    georgezhang006  commented on Aug. 3, 2020, 6:13 p.m.

    Would Anyone be so kind and give me some tips on my code?

    Im struggling on passing batch 4 test case 13.


    • 1
      Togohogo1  commented on Aug. 4, 2020, 1:50 p.m.

      You are looping through every element in array and breaking when an element is larger than M (the upper bound). Since array is sorted in your code, think of a searching technique that is more efficient than a linear scan.