TLE '17 Contest 8 P3 - Curious Numbers

View as PDF

Submit solution


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

Author:
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
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

2
10

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.


Comments


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

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

    https://dmoj.ca/submission/2609021

    Im struggling on passing batch 4 test case 13.

    Thanks!


    • 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.