Bittijono

#stringBuilder?

def main():
    tavoite = int(input())
    pituus = 1;
    summa = 1
    a = 1
    b = 1
    while summa < tavoite:
        pituus+=1
        a, b = a + b, a
        summa += a
    print(lyhinjono(tavoite, [1], 1, 2, 1, pituus + 2))

#tavoite: tavoiteltava summa
#tähän asti lisätyt luvut
#viimeinen: listan viimeinen luku
#summa: lisättävä summa jos lisätään eri luku kuin viimeinen
#kokonaisSumma: listan kokonaisSumma
def lyhinjono(tavoite, lista, viimeinen, summa, kokonaisSumma, raja):
    if kokonaisSumma == tavoite:
        #print(lista)
        bittijono = ""
        edellinenBitti = "0"
        edellinenLuku = 0
        for luku in lista:
            if luku == edellinenLuku:
                bittijono += edellinenBitti
            else:
                edellinenLuku = luku
                if edellinenBitti == "0":
                    bittijono += "1"
                    edellinenBitti = "1"
                else:
                    bittijono += "0"
                    edellinenBitti = "0"
        return bittijono
    if kokonaisSumma > tavoite or (raja != 0 and len(lista) >= raja):
        return False
    #lisätään eri luku, jolloin arvo kasvaa summalla
    jono1 = lyhinjono(tavoite, lista + [summa], summa, summa + viimeinen, kokonaisSumma + summa, raja)
    if jono1:
        raja = len(jono1)
    #lisätään sama luku kuin edellinen, arvo kasvaa listan viimeisellä
    jono2 = lyhinjono(tavoite, lista + [viimeinen], viimeinen, summa + viimeinen, kokonaisSumma + viimeinen, raja)
    if jono2:
        return jono2
    return jono1

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

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: ACCEPTED

Test 22

Group: 3

Verdict: ACCEPTED

Test 23

Group: 3

Verdict: ACCEPTED

Test 24

Group: 3

Verdict: ACCEPTED

Test 25

Group: 3

Verdict: ACCEPTED

Test 26

Group: 3

Verdict: ACCEPTED

Test 27

Group: 3

Verdict: ACCEPTED

Test 28

Group: 3

Verdict: ACCEPTED

Test 29

Group: 3

Verdict: ACCEPTED

Test 30

Group: 3

Verdict: ACCEPTED

Test 31

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 33

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 4

Verdict: TIME LIMIT EXCEEDED