TLE '17 Contest 8 P3 - Curious Numbers - Olympiads 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 \leq Q \leq 10^{5})$ and $K$ $K$ $(1 \le K \le 10^{10})$ $(1 \leq K \leq 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 \leq M \leq N \leq 10^{10})$ .

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

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

Output Specification

On separate lines, print the answer to each query.

Sample Input

Copy

2 2
10 50
100 300

Sample Output

Copy

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.