TLE '17 Contest 8 P3 - Curious Numbers - DMOJ: Modern Online Judge

TLE '17 Contest 8 P3 - Curious Numbers

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

ZQFMGB12

Problem type

Fax McClad is a deep thinker.

Fax McClad, Croneria's most curious bounty hunter, is interested in 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$ ~12\,321~ is a palindrome, and $1\,234$ ~1\,234~ is not. Leading zeroes are not part of a palindrome. For example, $3\,130$ ~3\,130~ is not a palindrome.

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

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

Input Specification

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

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

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

For an additional $30\%$ ~30\%~ of the points, $N, M, K \le 10^6$ ~N, M, K \le 10^6~, $Q \le 10^3$ ~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$ ~11, 22, 33, 44~ are the only palindromes in between $10$ ~10~ and $50$ ~50~. Only $22$ ~22~ and $44$ ~44~ are divisible by $2$ ~2~.

Comments

1

georgezhang006 commented on Aug. 3, 2020, 10: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, 5: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.