Lukuvälit

#
#
#


def kysy():
    """
    Kysytään luvut
    :return:
    """
    syote_maara = int(input())

    valit = []
    for _ in range(syote_maara):
        syote = input().split()
        valit.append(
            (int(syote[0]), int(syote[1]))
        )
    return valit


# def tarkista(vali):
#     # Tarkistetaan kaikki luvut väliltä
#     count = 0
#     for n in range(vali[0], vali[1] + 1):
#         luku = str(n)
#
#         for numero in luku:
#             if numero not in ("0", "1"):
#                 sisältyy = False
#                 break
#             else:
#                 sisältyy = True
#         if sisältyy:
#             count += 1
#     return count

def tarkista(luku):
    """
    Lasketaan binääriä käyttäen.
    :param luku:
    :return count: 1 ja 0 sisältävien lukujen määrä
    """
    count = 0

    def määrät_alemmista(numeroinen):
        """
        Laskee alemmat binäärinkaltaiset luvut.
        :param numeroinen:
        :return:
        """
        # Lasketaan 0 mukaan
        count = 1
        for i in range(numeroinen):
            count += 2**i
        return count

    def binääriksi(numeroinen):
        """
        Kaikki binäärit n-numeroisessa luvussa.
        Palauttaa listan n-numeroisista binääreistä, jotka on tulkittu
        kokonaisluvuiksi.

        :param numeroinen:
        :return: list
        """
        # Pienin n-numeroinen binääri
        binääri = int("1" + "0" * (numeroinen - 1), 2)
        binäärit = []

        # Binäärit listaan
        while True:
            # Tulkitaan binääri kokonaislukuna
            kokonais = int(f"{binääri:b}")
            binäärit.append(kokonais)

            # Toinen binääri
            binääri += 1

            if len(f"{binääri:b}") > numeroinen:
                break
        return binäärit

    def binäärihaku(lista, haettava):
        """
        Etsii listasta alkion, jonka binäärin kymmenkantaiseksi tulkittu
        kokonaisluku on sama kuin haettava tai juuri haettavaa alempi.

        :param lista: Lista kymmenkantaisiksi tulkittuja binäärejä
        :param haettava: Kokonaislukuna haettava kohde
        :return:
        """
        # Suoritetaan binäärihaku välillä [a,b], missä a ja b ovat listan
        # alkioita
        a = 0
        b = len(lista) - 1

        while True:
            keski = round((a + b) / 2)
            # print("a", a)
            # print("b", b)
            # print("k", keski)
            # print()

            # Onko haettavan ympärillä vain kaksi indeksiä
            if b - a <= 1:
                return a

            # Haettava on välillä [a,keski[
            if haettava < lista[keski]:
                b = keski
                # print("<-")
            # Haettava on välillä ]keski,b]
            elif lista[keski] < haettava:
                a = keski
                # print("->")
            # Haettava on keski
            else:
                return keski

    # Numeroiden määrä
    num_lkm = len(str(luku))

    # Suurin määrä n-numeroisessa luvussa
    määrien_ylä = int("1" * num_lkm)
    if luku >= määrien_ylä:
        count = määrät_alemmista(num_lkm)
    # Numero 0 rikkoo koko jutun
    elif luku == 0:
        count = 1
    # Samoin negatiiviset
    elif luku < 0:
        count = 0
    else:
        # Tutkitaan tapauskohtaisesti
        #############################

        # Alempien numeroiden määrä
        count += määrät_alemmista(num_lkm - 1)

        binäärilista = binääriksi(num_lkm)
        # print("Binäärilista:")
        # for i in range(len(binäärilista)):
        #     print(f"{binäärilista[i]:b}")

        # Suoritetaan binäärihaku, joka antaa binäärilistan alkion; lisätään 1
        count += binäärihaku(binäärilista, luku) + 1

    # print("Num_lkm:", num_lkm)
    # print("Binääri:", määrien_ylä)
    # print("Count:", count)
    # print()
    return count


def main():
    välit = kysy()

    # print(välit[0])
    for väli in välit:
        print(tarkista(väli[1]) - tarkista(väli[0] - 1))


main()

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: 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