Bittijono

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

//tavoite: tavoiteltava summa
//lista: lisätyt luvut
//viimeinen: listan viimeinen luku
//summa: lisättävä summa jos lisätään eri luku kuin viimeinen
//kokonaisSumma: listan kokonaissumma
//raja: raja listan pituudelle (missä vaiheessa lopetetaan etsintä)

deque<int> lyhinjono(ll tavoite, deque<int> lista, ll viimeinen, ll summa, ll kokonaissumma, ll raja, int bitti) {
    int length = lista.size();
    if (kokonaissumma == tavoite) {
        return lista;
    }
    if (kokonaissumma > tavoite || length >= raja) {
        lista.clear();
        return lista;
    }

    int uusiBitti = 1;
    if (bitti == 1) {
        uusiBitti = 0;
    }
    //lisätään eri luku, arvo kasvaa summalla
    lista.push_back(uusiBitti);
    deque<int> jono1 = lyhinjono(tavoite, lista, summa, summa + viimeinen, kokonaissumma + summa, raja, uusiBitti);
    if (!jono1.empty()) {
        raja = jono1.size();
    }
    lista.pop_back();
    lista.push_back(bitti);
    deque<int> jono2 = lyhinjono(tavoite, lista, viimeinen, summa + viimeinen, kokonaissumma + viimeinen, raja, bitti);
    if (!jono2.empty()) {
        return jono2;
    }
    return jono1;
}

int main() {
    ll tavoite;
    cin >> tavoite;
    ll pituus = 1;
    ll summa = 1;
    ll a = 1;
    ll b = 1;
    while (summa < tavoite) {
        pituus++;
        ll c = a;
        a += b;
        b = c;
        summa += a;
    }
    deque<int> lista;
    lista.push_back(1);
    deque<int> jono = lyhinjono(tavoite, lista, 1, 2, 1, pituus + 2, 1);
    for (unsigned int i = 0; i < jono.size(); i++) {
        cout << jono[i];
    }
    cout << endl;
}

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