Lukuvälit

import itertools
import math
# import random
# import time

# cache = dict()
def get_products(len):
    # if len in cache:
        # return cache[len]

    products = itertools.product(['0', '1'], repeat=len)
    res = list(map(lambda x: int(''.join(x)), products))
    # cache[len] = res
    return res

def decide_step(dist, b):
    if dist <= 1 or b <= 10000:
        return 1

    if b > 1000000:
        return pow(2, 18 - len(str(b)))

    return max(1, int(math.floor(math.log(dist))))

def solve(a, b):
    str_len = len(str(b))
    products = get_products(str_len)
    products_len = len(products)

    biggest_num = int('1' * str_len)
    b = min(b, biggest_num)

    try:
        startIndex = 0
        step = decide_step(a, b)
        # print('start with start step {}'.format(step))
        while products[startIndex] < a:
            startIndex = min(products_len - 1, startIndex + step)
            if startIndex + 1 == products_len:
                break

            step = decide_step(abs(a - products[startIndex]), b)
            # print('new start step is {}, cur index is {}'.format(step, startIndex))

        while startIndex > 0 and products[startIndex] >= a:
            startIndex -= 1

        if products[startIndex] < a:
            startIndex += 1

        endIndex = -1
        step = decide_step(b, b)
        # print('start with end step {}'.format(step))
        # print(products[endIndex], b)
        if products[endIndex] > b:
            while products[endIndex] > b:
                endIndex = max(-products_len + 1, endIndex - step)
                # print('new end step: {}'.format(endIndex))
                if endIndex - 1 == -products_len:
                    break

                step = decide_step(abs(b - products[endIndex]), b)
                # print('new end step is {}'.format(step))
            
            # print(products[endIndex], b)
            while endIndex < 0 and products[endIndex] <= b:
                # print('we need to go BACK: {}, {}'.format(endIndex, products[endIndex]))
                endIndex += 1
        else:
            endIndex = products_len

        # print(a, b)
        # print(products_len, startIndex, endIndex)
        # print(products)
        # print(products[startIndex:endIndex])
        return products_len + min(0, endIndex) - startIndex
    except IndexError:
        return 0

# def slowsolve(a, b):
#     count = 0
#     # res = list()
#     for x in range(a, b):
#         if all(val == '1' or val == '0' for val in set(str(x))):
#             count += 1
#             # res.append(x)

#     # print(res)
#     return count

# for x in range(0, 10000):
#     a = random.randint(pow(10, 1), pow(10, random.randint(3, 5)))
#     b = random.randint(pow(10, 5), pow(10, 8))

#     start = time.time()
#     our_solution = solve(a, b + 1)
#     print('our solution for [{}, {}]: {} ({}s)'.format(a, b, our_solution, str(time.time() - start)))

#     start = time.time()
#     slow_solution = slowsolve(a, b)
#     print('slow solution: {} ({}s)'.format(slow_solution, str(time.time() - start)))

#     if our_solution != slow_solution:
#         break

count = int(raw_input())
for x in range(0, count):
    a, b = [int(x) for x in raw_input().split()]
    print(solve(a, b))

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

Test 12

Group: 1, 2, 3

Verdict: ACCEPTED

Test 13

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 2, 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 2, 3

Verdict: ACCEPTED

Test 18

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 2, 3

Verdict: ACCEPTED

Test 20

Group: 2, 3

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 109, in <module>
    print...

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 3

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 109, in <module>
    print...

Test 27

Group: 3

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 109, in <module>
    print...

Test 28

Group: 3

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 109, in <module>
    print...