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 > 10000000:
        return pow(2, 20 - 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: ACCEPTED

Test 14

Group: 2, 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: ACCEPTED

Test 16

Group: 2, 3

Verdict: ACCEPTED

Test 17

Group: 2, 3

Verdict: ACCEPTED

Test 18

Group: 2, 3

Verdict: ACCEPTED

Test 19

Group: 2, 3

Verdict: ACCEPTED

Test 20

Group: 2, 3

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

Test 27

Group: 3

Verdict: ACCEPTED

Test 28

Group: 3

Verdict: ACCEPTED