Bittijono

def main():
    tavoite = int(input())
    minimi = 1
    maksimi = 28
    while maksimi != minimi:
        pituus = (minimi + maksimi) // 2
        jono = (pituus//2)*"10" + (pituus%2)*"1"
        if alijonot(jono) >= tavoite:
            maksimi = pituus
        else:
            minimi = pituus + 1

    alku = 2**(pituus-1)
    loppu = 2*alku
    kaytetyt = set()
    while True:
        #format (i, 'b') muuttaa binääristringiksi (3 --> 11)
        #2**(3-1) = 100, 2**3 - 1 = 111
        #väliltä 000-011 ei tarvitse, koska 111 ja 000 määrät ovat samat
        jonot = [format(j, 'b') for j in range(alku, loppu)]
        for j in range(len(jonot)):
            jono = jonot[j]
            if jono in kaytetyt:
                continue
            if alijonot(jono) == tavoite:
                print(jono)
                return
            if j % 2 != 0:
                kaytetyt.add(jono[::-1])
            else:
                #käännetään merkit miinuslaskulla (11111 - 10110 = 01001)
                #sitten peilaus: 01001 --> 10010
                kaytetyt.add(("0" + format(loppu - 1 - (alku + j), 'b'))[::-1])
        alku = loppu
        loppu *= 2

def alijonot(bittijono):
    jonot = set([1])
    prev0 = set()
    prev1 = set()
    for i in range(0, len(bittijono)):
        luku = bittijono[i]
        temp = jonot.copy()
        if luku == "1":
            jonot.update(set([jono*2 + 1 for jono in jonot - prev1]))
            prev1 = temp
        else:
            jonot.update(set([jono*2 for jono in jonot - prev0]))
            prev0 = temp
    return len(jonot) - 1

    jonot = set([1])
    for i in range(0, len(bittijono)):
        luku = int(bittijono[i])
        jonot.update(set([jono * 2 + luku for jono in jonot]))
    return len(jonot) - 1

    """
    jonot = set(["1"])
    prev0 = set()
    prev1 = set()
    for i in range(1, len(bittijono)):
        merkki = bittijono[i]
        temp = jonot.copy()
        if merkki == "0":
            jonot.update(set([jono + merkki for jono in jonot - prev0]))
            prev0 = temp
            jonot.add(merkki)
        else:
            jonot.update(set([jono + merkki for jono in jonot - prev1]))
            prev1 = temp
    return jonot
    """

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

Test 28

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 3

Verdict: TIME LIMIT EXCEEDED

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