When finding the number of solutions in the range [L,R], we can rewrite it as $$$f(R)-f(L-1)$$$ where $$$f(x)$$$ is a function that returns the number of lucky numbers from 1 to x. Now, the next step for us is to define $$$f(x)$$$.

def f(x):
  ans = x
  non_lucky = [
    1, 2, 4, 5, 7, 8,   # one-digit non-lucky numbers
    11, 14, 17, 41, 44, 47, 71, 74, 77,   # two-digit non-lucky numbers from group xx
    22, 25, 28, 52, 55, 58, 82, 85, 88  # two-digit non-lucky numbers from group yy
  ]
  for num in non_lucky:
    if num<=x:
      ans-=1
  return ans

for testcase in range(int(input())):
  L, R = map(int,input().split())
  print(f(R)-f(L-1))

P.S this is my first time writing something like this, if there are some improvements I can do please tell me ^ ^

Problem is too easy, answer will be (r-l)/3 + (r%3 ! = l%3) because all numbers divisible by 3 can be calculated by dividing the range by 3.

I'm almost certainly overcomplicating this but this was my first thought. (EDIT: Reading the other solution I 100 percent overcomplicated it :|, still a good trick to know)

This problem can be solved using digit DP. First, acknowledge that if a number is divisible by 3, the sum of its digits is divisible by 3. This means that when placing a number, we can handle it mod 3 due to how modular addition works.

Now we can get into the dp states. Like most digit dp, we have to keep a state of if we have gone under the number, and also one if we have placed a non zero number, along with the position of the digit that we are placing.

We'll need 3 additional states (note that if there is a suffix that is 0 mod 3, then we would already have a substring divisible by three, and the completed flag would be set) - completed: do we already have a substring that is divisible by 3 - suffix_mod_3_1: from the elements we have already placed, is there any suffix that is equal to 1 mod 3 - suffix_mod_3_2: from the elements we have already placed, is there any suffix that is equal to 2 mod 3

The purpose of the suffix states are the following, imagine that the number that we've created so far is 52. In this case there is a suffix equal to 1 mod 3 (52) and a suffix equal to 2 mod 3 (2). If we were to add a number to the end, let's say a, then - If a mod 3 is 1, we'd have a substring equal to 0 mod 3 (2a) - If a mod 3 is 2, we'd have a substring equal to 0 mod 3 (52a) - If a mod 3 is 3, we'd have a substring equal to 0 mod 3 (a)

Transitions can be handled using the same idea, and from there, it's standard Digit DP.

I probably made a couple of mistakes explaining so my apologies if I did

all numbers over >100 are lucky numbers.

Proof:

Lemma 1: All digits that are multiples of three have digit sums that are multiples of 3. Proof: Look It up.

Let's store an arbritary three digit number x's digits. Each digit will have arbritary value mod 3. Let's take the prefix sum of the digit written left to right. We will get four prefix sums 0, x[0]%3,(x[0]+x[1])%3,(x[0:2])%3. There are three posible values mod 3 (0,1,2), but we have four prefix sums, so by pigeonhole principle since 4 > 3, there is at least one pair of prefixes that have the same sum. Then, by prefix sums there is a substring that has a digit sum that is a multiple of 3, and thus the substring is a multiple of 3.

Therefore, the correct algorithm is brute force to 100, and include all other numbers, which should pass.