Onnenluku

#!/usr/bin/env python3

# onnenluku
# tasan kahta numeroa sisältävien lukujen määrä välillä a..b

# esim. 1274
# rekursiolla yhdistelmien määrä eri etenemishaaroista:
# - mitkä numerot on jo lukittu tässä haarassa
# - onko paikan numerorajoite vielä voimassa (esim. 1274: 12xx on, 11xx ei)

def laske(numerot_nurin, lukitut=[], rajoite=True):
    '''palauta tuplanumerolukujen määrä välillä 0...n

    numerot_nurin: n-luvun numerot lopusta alkuun, esim. 1274 -> [4, 7, 2, 1]
    lukitut: 0..2 uniikkia, yhdistelmiin lukittua numeroa
    rajoite: edetään numerot_nurin-luvun asettamaa ylärajaa pitkin

    '''

    if not numerot_nurin:
        # yhdistelmä valmis, saatiinko se kahdella kasaan?
        return 1 if len(lukitut) == 2 else 0

    yht = 0
    nykyinen = numerot_nurin.pop()

    for x in range(1, 10):
        uusi_numero = x not in lukitut
        if len(lukitut) > 1 and uusi_numero:
            continue
        if rajoite and x > nykyinen:
            continue

        if uusi_numero:
            lukitut.append(x)
        yht += laske(numerot_nurin, lukitut, rajoite and x == nykyinen)
        if uusi_numero:
            lukitut.pop()

    if not lukitut:
        # ylärajaa lyhyemmät eli aina sitä pienemmät yhdistelmät
        yht += laske(numerot_nurin, lukitut, False)

    numerot_nurin.append(nykyinen)
    return yht

def hidas(x):
    return sum(1 for x in range(1, x + 1) if len(set(str(x))) == 2 and '0' not in str(x))

def numerot_nurin(x):
    return [int(c) for c in str(x)[::-1]]

def main():
    a, b = map(int, input().strip().split())

    ca = laske(numerot_nurin(a - 1), [])
    cb = laske(numerot_nurin(b), [])
    print(cb - ca)

if __name__ == '__main__':
    main()

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED