Interaktivni algoritmi

U ovoj sekciji ćete naći **detaljno obrađene zadatke interaktivnog tipa** — problemi u kojima vaš program postavlja upite, čeka odgovore i adaptira strategiju u toku izvršenja. Interaktivni algoritmi su važan deo takmičenja i zahtevaju pažljivo planiranje broja upita, konstrukciju diskriminativnih testova i otpornost na nepredviđene odgovore.

Napomena: Zаdаci na ovoj strani su preuzeti sa kolekcije Kilonova — Interactive Problems List. Svi zadaci ovde su obrađeni sa objašnjenjima i rešenjima.

Pregled zadataka interaktivnih algoritama pomaže vam da savladate sledeće koncepte:

• Protokol interakcije: kako postavljati pitanja i obrađivati odgovore.
• Binarna pretraga u interaktivnom režimu.
• Strategije robusnosti protiv slučajnih ili varijabilnih odgovora (npr. majority voting, ponavljanje upita).
• Kombinovanje upita za lokalizaciju ciljnog segmenta ili pozicije.

Svaki zadatak je predstavljen sa **kompletnim uputstvom, idejama za rešavanje i gotovim kodom** — idealno za učenje i vežbu strateških tehnika u interaktivnim uslovima.

Zadatak 1 – Igra sa Džokerom

Opis problema

Korisnici igraju igru sa Džokerom. On im je dao broj N (5 ≤ N ≤ 1000) i rekao da ima skrivena dva broja L i R (0 ≤ L ≤ R ≤ N−1). Cilj igre je da korisnici pronađu ta dva broja.

Korisnici mogu postavljati pitanja sledećeg oblika: daju niz od N brojeva a_0, a_1, …, a_{N−1} i pitaju: „Reci mi koji je minimum brojeva aL, aL+1, …, aR.“ Problem je što u jeziku Džokera ne postoji reč za minimum — on razume reč ekstrem, pa će na svako pitanje nasumično odgovoriti ili minimumom ili maksimumom segmenta [L,R] iz niza.

Džoker prihvata kao tačan odgovor svaku pretpostavku (L', R') koja zadovoljava:

|L − L'| + |R − R'| ≤ 1

Zadatak

Na osnovu ovih informacija korisnici treba da pronađu par (L', R') koji Džoker smatra tačnim, koristeći što manji broj pitanja.

Specifikacija

• Vreme izvršavanja: 1 sekunda
• Memorijski limit: 1024 MB
• Ulaz:stdin
• Izlaz:stdout

Interakcija

Korisnici mogu koristiti sledeće funkcije za interakciju sa Džokerom:

• int query(std::vector<int> a) – prima niz brojeva i vraća ili minimum ili maksimum segmenta [L,R], nasumično odabrano od strane Džokera.
• void answer(int L, int R) – poziva se sa pretpostavljenim parom (L,R) koji korisnici smatraju tačnim.

Korisnici treba da implementiraju samo funkciju solve(int N). Nije potrebno implementirati main funkciju. Sav kod se piše u fajlu solutie.cpp. Korisnici mogu definisati i dodatne funkcije i globalne promenljive.

Primer interakcije

Primer: N = 5, skriveni brojevi L = 1, R = 3. Segment [L,R] odgovara nizu {3, 8, 1}.

Ako korisnici pozovu:

int res = query({5, 3, 8, 1, 6});

Džoker vraća ili 1 (minimum) ili 8 (maksimum).

Ako korisnici pozovu:

answer(1, 3);

Prikazuje se:

Correct

// Primer probabilističke strategije za igru sa Džokerom
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Stub funkcija koja simulira komunikaciju sa Džokerom.
// U stvarnom zadatku ovde ide I/O sa interaktivnim okruženjem.
int send_query(const vector<int>& a) {
    return 0; // simulacija
}

bool verify_candidate(int l, int r, int K) {
    int ok = 0;
    for (int t = 0; t < K; ++t) {
        vector<int> a; 
        int res = send_query(a);
        if (false) ++ok; // placeholder
    }
    return ok * 2 > K;
}

int main() {
    vector<pair<int,int>> candidates; 
    int K = 5;
    for (auto [l,r] : candidates) {
        if (verify_candidate(l, r, K)) {
            cout << "Pronađen kandidat: " << l << " " << r << "\n";
            break;
        }
    }
    return 0;
}

Za detaljnije rešenje i objašnjenje zadatka Joker, pročitaj celu stranicu sa rešenjem .

Zadatak 2 – Plockchain i Lina

Vasilije je prijatelj Line. Nedavno je otvorio nalog na Pinance kako bi provodio više vremena ulažući u kriptovalute nego u crkvi. Na njegovo iznenađenje, jednog dana je primetio da su njegove investicije donele plodove. Zatečen ovim događajem, odlučio je da analizira događaje koji su se odigrali u Plockchain-u i doveli ga do ovih visina.

Vasilije nam je objasnio da možemo da zamislimo da Plockchain funkcioniše na sledeći način:

• Na početku u sistemu postoji N zahteva za transakcijama, indeksiranih od 1 do N. Svaki zahtev i ima proviziju W_i i jedinstveni zahtev od koga direktno zavisi P_i.
• Kaže se da je zahtev sa indeksom 1 prvobitan i da nema nikakvu zavisnost.

Vasilije je uočio da se u Plockchain-u događaju tri tipa operacija:

1. Pojavljuje se novi zahtev sa provizijom C, čija je direktna zavisnost T. Indeks tog zahteva biće N + t + 1, gde je t broj do sada dodatih zahteva ovim postupkom. Tako prvi dodati zahtev dobija indeks N + 1.
2. Menja se provizija zahteva sa indeksom a iz W_a u C.
3. Briše se zahtev sa indeksom a. Garantuje se da ne postoji zahtev j tako da je P_j = a (tj. nijedan zahtev ne zavisi od njega).

Lina, zadivljena Vasilijevim objašnjenjima, počela je često da postavlja sledeće pitanje:

„Ako posmatramo sve zahteve koji trenutno postoje u sistemu, koliku bi proviziju dobio haker ako bi izvršio sve zahteve koji se nalaze na najviše H nivoa zavisnosti naniže u odnosu na zahtev X?“

Kažemo da se zahtev A nalazi na najviše x zavisnosti naniže u odnosu na B ako i samo ako:

• x ≥ 0 i A = B, ili
• x ≥ 1 i P_A se nalazi na najviše x - 1 zavisnosti naniže u odnosu na B.

Pretpostavlja se da haker dobija zbir provizija svih izvršenih zahteva. Pitanja Line ne menjaju stanje sistema. Takođe, konstanta H je ista za svako pitanje.

Zadatak

Potrebno je da pronađeš odgovore na pitanja koja Lina postavlja nakon serije operacija.

Ulaz

• Prvi red: N, Q i H – broj početnih zahteva, broj operacija i konstanta H.
• Drugi red: N brojeva – provizije W_i za svaki zahtev.
• Treći red: N - 1 brojeva – P_i+1, zahtev od koga zavisi zahtev i+1.
• Zatim sledi Q redova – svaka operacija je u obliku:
  • t = 1: C T (novi zahtev sa provizijom i zavisnošću)
  • t = 2: a M (menja se provizija zahteva a)
  • t = 3: a (zahtev a se briše)
  • t = 4: X (pitanje Line za zahtev X)

Izlaz

Za svako pitanje (operacija sa t = 4) ispisati ukupan zbir provizija za odgovarajuće zahteve.

Ograničenja

• 2 ≤ N ≤ 200 000
• 1 ≤ Q ≤ 200 000
• 1 ≤ H ≤ N
• 0 ≤ C, M ≤ 1 000 000 000
• T < R pri dodavanju novog zahteva
• 1 ≤ P_i < i
• 0 ≤ W_i ≤ 1 000 000 000
• Zahtevi u operacijama uvek postoje u tom trenutku
• Nikada se ne briše zahtev 1
• Nikada se ne briše zahtev od koga zavisi neki drugi

Primer

stdin:
8 7 2
10 12 4 20 4 5 11 10
1 1 3 4 2 6 6
1 50 4
4 3
2 1 50
4 1
2 6 35
1 5 7
4 6

stdout:
78
91
61
  

Objašnjenje

Za prvu upitnu operaciju, zahtevi koji su na najviše 2 nivoa zavisnosti naniže u odnosu na zahtev 3 su: 3 (provizija 4), 4 (20), 9 (50), 5 (4). Ukupno: 4 + 20 + 50 + 4 = 78.

Copy
// solutie.cpp (implementacija jednostavnog pristupa sa sumInRange)
// Napomena: funkcionalno rešenje za takmičarski grader treba da koristi ulaz/izlaz
// kako je definisano u opisu zadatka. Ovaj kod radi stdin/stdout.

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q, H;
    if (!(cin >> N >> Q >> H)) return 0;

    // maksimalan broj cvorova (inicijalni + dodati)
    // u najgorem slucaju doda se Q novih nodova
    int maxNodes = N + Q + 5;

    vector w(maxNodes, 0);           // tezina/provizija za svaki cvor (1-based)
    vector parent(maxNodes, 0);            // parent[i], parent[1] = 0
    vector sumInRange(maxNodes, 0);  // sum svih potomaka u rastojanju <= H (ukljucujuci i se)
    vector exists(maxNodes, false);       // da li cvor trenutno postoji (posle brisanja se false)

    // ucitavanje pocetnih tezina
    for (int i = 1; i <= N; ++i) {
        long long val; cin >> val;
        w[i] = val;
        exists[i] = true;
    }

    // ucitavanje roditelja: P_{i+1} za i=1..N-1 => parent[2..N]
    parent[1] = 0;
    for (int i = 2; i <= N; ++i) {
        int p; cin >> p;
        parent[i] = p;
    }

    // inicijalizacija sumInRange: za svaki cvor u, dodaj w[u] u svakog od njegovih prethodnika na udaljenosti <= H
    for (int u = 1; u <= N; ++u) {
        long long val = w[u];
        int cur = u;
        int steps = 0;
        while (cur != 0 && steps <= H) {
            sumInRange[cur] += val;
            cur = parent[cur];
            ++steps;
        }
    }

    int nextIndex = N; // zadnji indeks dodeljen
    for (int qi = 0; qi < Q; ++qi) {
        int t; cin >> t;
        if (t == 1) {
            // dodavanje novog zahteva
            long long C; int T;
            cin >> C >> T;
            ++nextIndex;
            int R = nextIndex;
            w[R] = C;
            parent[R] = T;
            exists[R] = true;
            // Ažuriraj sumInRange za sve ancestor-e do udaljenosti H
            int cur = R;
            int steps = 0;
            while (cur != 0 && steps <= H) {
                sumInRange[cur] += C;
                cur = parent[cur];
                ++steps;
            }
        } else if (t == 2) {
            // izmena tezine
            int a; long long M;
            cin >> a >> M;
            long long delta = M - w[a];
            w[a] = M;
            // propagate delta ka ancestor-ima do udaljenosti H
            int cur = a;
            int steps = 0;
            while (cur != 0 && steps <= H) {
                sumInRange[cur] += delta;
                cur = parent[cur];
                ++steps;
            }
        } else if (t == 3) {
            // brisanje cvora (garantovano da je list)
            int a; cin >> a;
            if (!exists[a]) continue;
            long long val = w[a];
            // oduzmi val od ancestor-a do udaljenosti H
            int cur = a;
            int steps = 0;
            while (cur != 0 && steps <= H) {
                sumInRange[cur] -= val;
                cur = parent[cur];
                ++steps;
            }
            exists[a] = false;
            // opcionalno w[a] = 0; (ostavimo vrednost, ali markiramo da ne postoji)
        } else if (t == 4) {
            // upit
            int X; cin >> X;
            // direktno vrati sumInRange[X] (ako cvor postoji)
            long long ans = exists[X] ? sumInRange[X] : 0LL;
            cout << ans << '\n';
        }
    }

    return 0;
}
    

Zadatak 3 – Boja

Opis problema

Vremensko ograničenje: 1s
Memorijsko ograničenje: 512MB
Ulaz: stdin
Izlaz: stdout

Imaš kolekciju od n posuda, svaka sadrži količinu x_i litara boje. Na raspolaganju imaš q tipova kofica, gde kofica tipa i može da sadrži tačno y_i litara. Postoji beskonačno mnogo kofica svakog tipa.

Da bi napravio nove nijanse, možeš odabrati bilo koju kontinuiranu podsekvencu posuda i pomešati boju iz njih. Zatim biraš jedan tip kofice i proveravaš da li možeš upakovati svu dobijenu boju koristeći samo kofice tog tipa (bez ostatka).

Zadatak

Za svaki tip kofice, odredi u koliko načina se može odabrati podsekvenca posuda tako da ukupna količina boje može biti potpuno upakovana u kofice tog tipa.

Ulaz

Prva linija: dva cela broja n i q  
Druga linija: n brojeva x₁, x₂, …, xₙ  
Treća linija: q brojeva y₁, y₂, …, y_q
  

Izlaz

Program ispisuje q redova — za svaku koficu broj podsekvenci koje se mogu potpuno upakovati.

Ograničenja

• 1 ≤ N, Q ≤ 8000
• 1 ≤ x_i, y_i ≤ 10⁶

Podzadaci

• (10 poena) q = 1 i y₁ > Σx_i
• (20 poena) N ≤ 60, Q ≤ 100
• (30 poena) N ≤ 500, Q ≤ 1000
• (40 poena) Bez dodatnih ograničenja

Primer

Ulaz
5 2
4 2 3 6 8
4 5

Izlaz
2
2
  

// Rešenje zadatka "Vopsea (Boja)"
#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector x(n + 1, 0), prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        prefix[i] = prefix[i - 1] + x[i];
    }

    vector y(q);
    for (int i = 0; i < q; i++) cin >> y[i];

    for (int j = 0; j < q; j++) {
        long long cap = y[j];
        long long count = 0;
        for (int l = 1; l <= n; l++) {
            for (int r = l; r <= n; r++) {
                long long sum = prefix[r] - prefix[l - 1];
                if (sum % cap == 0) count++;
            }
        }
        cout << count << "\n";
    }

    return 0;
}
      

Za detaljnije rešenje i objašnjenje zadatka Boja, pročitaj celu stranicu sa rešenjem .

Zadatak 4 – Maksimizacija BTC kroz kripto trgovinu

Vremensko ograničenje: 2s
Memorijsko ograničenje: 512MB
Ulaz: stdin
Izlaz: stdout

Opis problema

Alex počinje sa tačno 1 BTC i želi da poveća svoj kapital kroz niz od N dana trgovanja. Na platformi postoji K kriptovaluta, numerisanih od 1 do K, pri čemu je 1 rezervisan za BTC.

Svakog dana dobija matricu A dimenzije K × K, gde A[i][j] označava kurs po kojem može pretvoriti iznos x u valuti i u A[i][j] * x valute j. Svaka transakcija traje jedan ceo dan, pa sredstva konvertovana danas ne mogu biti ponovo korišćena istog dana. Alex može i odlučiti da ne obavi nikakvu transakciju tog dana.

Nakon N dana Alex želi da završi sa maksimalnom količinom BTC. Potrebno je odrediti tu maksimalnu količinu.

Ulaz

• Prva linija: N i K, broj dana i broj kriptovaluta.
• Zatim slede N matrica dimenzije K × K realnih brojeva, gde A[i][j] predstavlja kurs za konverziju.

Izlaz

Ispisati realan broj — maksimalnu količinu BTC koju Alex može imati nakon N dana. Odgovor mora imati relativnu grešku najviše 10-6.

Ograničenja

• 1 ≤ N ≤ 80
• 1 ≤ K ≤ 50
• 10-5 < A[i][j] < 105
• x ≤ 1013

Primer

Ulaz:
1 3
2.0 1.0 2.5
1.4 1.0 3.14159265359
3.0 3.0 3.0

Izlaz:
2.0000000000
  

Objašnjenje primera

U primeru postoji jedan dan i tri valute. Ako Alex iskoristi današnje kurseve direktno za BTC→BTC po faktor 2.0, njegov iznos BTC će se uvećati sa 1 na 2 BTC. To je u ovom primeru optimalno.

// Rešenje zadatka "Maksimizacija BTC kroz kripto trgovinu"
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    // A[day][from][to]
    vector>> A(N, vector>(K, vector(K)));
    for (int d = 0; d < N; d++) {
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < K; j++) {
                cin >> A[d][i][j];
            }
        }
    }

    // dp[day][currency] - maximum amount of each currency at the end of 'day'
    vector> dp(N + 1, vector(K, 0.0));
    dp[0][0] = 1.0; // start with 1 BTC (index 0 corresponds to currency 1 in statement)

    for (int d = 1; d <= N; d++) {
        // carry over the possibility of doing nothing for each currency
        for (int c = 0; c < K; c++) dp[d][c] = max(dp[d][c], dp[d-1][c]);

        // try all conversions using the rates from day d-1
        for (int i = 0; i < K; i++) {
            if (dp[d-1][i] == 0.0) continue; // optional micro-optimization
            for (int j = 0; j < K; j++) {
                dp[d][j] = max(dp[d][j], dp[d-1][i] * A[d-1][i][j]);
            }
        }
    }

    cout << fixed << setprecision(10) << dp[N][0] << "\n";
    return 0;
}
      

Za detaljnije rešenje i objašnjenje zadatka Maksimizacija BTC kroz kripto trgovinu, pročitaj celu stranicu sa rešenjem .

Zadatak 5 – Simetrično punjenje

Vremensko ograničenje: 0.2s    Memorijsko ograničenje: 256MB
Ulaz: stdin    Izlaz: stdout

Opis problema

Miša je dobio od Svetog Nikole skup od N × M čaša, koje je poređao u obliku matrice sa N redova i M kolona. Na raspolaganju ima dva tipa mleka u neograničenoj količini: mleko A i mleko B. Svaka čaša može biti napunjena ili mlekom A ili mlekom B. Označimo sa L[i][j] tip mleka u čaši na poziciji (i, j).

Miša želi da zna na koliko različitih načina može da napuni svih N × M čaša, ako mora da ispoštuje Q ograničenja tipa:

Svako ograničenje je dato četvorkom brojeva a b c d i predstavlja podmatricu određenu sa:

• donji levi ugao na poziciji (a, b),
• gornji desni ugao na poziciji (c, d).

U svakoj podmatrici čaše moraju činiti sliku simetričnu u odnosu na horizontalnu i vertikalnu osu. Formalno:

• L[a + i][j] = L[c - i][j] za svako 0 ≤ i ≤ c − a i b ≤ j ≤ d.
• L[i][b + j] = L[i][d - j] za svako a ≤ i ≤ c i 0 ≤ j ≤ d − b.

Potrebno je izračunati broj načina da se sve čaše popune tako da su ispunjena sva ograničenja. Rezultat treba dati modulo 998244353.

Ulaz

• Prvi red: tri cela broja N M Q — broj redova, broj kolona i broj ograničenja.
• Sledećih Q redova: po četiri cela broja a b c d — koordinate donjeg levog i gornjeg desnog ugla podmatrice.

Izlaz

Ispisati jedan ceo broj: broj načina da se napune čaše uz poštovanje svih ograničenja, modulo 998244353.

Ograničenja

• 1 ≤ N, M ≤ 300
• 1 ≤ Q ≤ 30000
• 1 ≤ a ≤ c ≤ N
• 1 ≤ b ≤ d ≤ M

Podzadaci

Primer 1

stdin
4 5 2
1 2 3 4
1 1 4 5

stdout
16
  

Primer 2

stdin
10 10 3
1 1 4 4
5 5 10 10
8 1 10 3

stdout
229805564
  

Prikaži / sakrij uputstvoPrikaži / sakrij rešenje

// Simetrično punjenje — DSU (Union-Find) pristup
// Ideja:
// Svako ograničenje nameće jednakosti između određenih ćelija.
// Te jednakosti se modeluju pomoću DSU strukture.
// Svaka nezavisna DSU komponenta može biti A ili B → 2 izbora.

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

const int MOD = 998244353;

/*
 * DSU (Disjoint Set Union) struktura
 * p[x]  – roditelj čvora x
 * sz[x] – veličina komponente (koristi se za union by size)
 */
struct DSU {
    vector<int> p, sz;

    DSU(int n) : p(n), sz(n, 1) {
        iota(p.begin(), p.end(), 0);
    }

    // Pronalaženje predstavnika skupa (path compression)
    int find(int x) {
        if (p[x] == x) return x;
        return p[x] = find(p[x]);
    }

    // Spajanje dva skupa
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;

        // Manji skup se kači na veći
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, Q;
    cin >> N >> M >> Q;

    int total = N * M;
    DSU dsu(total);

    // Mapiranje 2D koordinata (i, j) u 1D indeks
    auto id = [&](int i, int j) {
        return (i - 1) * M + (j - 1);
    };

    // Obrada svih ograničenja
    for (int q = 0; q < Q; q++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        // Horizontalna simetrija (gornji i donji redovi)
        for (int i = 0; i <= c - a; i++) {
            for (int j = b; j <= d; j++) {
                dsu.unite(
                    id(a + i, j),
                    id(c - i, j)
                );
            }
        }

        // Vertikalna simetrija (leva i desna kolona)
        for (int i = a; i <= c; i++) {
            for (int j = 0; j <= d - b; j++) {
                dsu.unite(
                    id(i, b + j),
                    id(i, d - j)
                );
            }
        }
    }

    // Brojanje različitih DSU komponenti
    vector<char> seen(total, 0);
    int components = 0;

    for (int i = 0; i < total; i++) {
        int root = dsu.find(i);
        if (!seen[root]) {
            seen[root] = 1;
            components++;
        }
    }

    // Računanje 2^components mod MOD
    long long result = 1;
    long long base = 2;
    int exp = components;

    while (exp > 0) {
        if (exp & 1) result = (result * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }

    cout << result << "\n";
    return 0;
}

    

Zadatak 6 – Etiketiranje

Time limit: 0.1s    Memory limit: 64MB
Input: stdin    Output: stdout

Zadatak

Miki je pripremio N tegli i želi da ih etiketira. Na raspolaganju ima K etiketa, numerisanih od 1 do K. Proces etiketiranja teče ovako:

1. Miki bira prvo mesto idx₁ (1 ≤ idx₁ ≤ N) i postavlja etiketu broj 1.
2. Za svaku sledeću etiketu t = 2..K bira se novo mesto idx_t tako da važi |idx_t − idx_{t−1}| = 1. Na to mesto postavlja etiketu t, zamenjujući postojeću ako je ima.

Denis predlaže krajnju konfiguraciju etiketa e₁, e₂, …, e_N (neetiketirane tegle imaju oznaku 0). Potrebno je izračunati koliko različitih procesa može dovesti do te konfiguracije. Rezultat dati modulo 998244353.

Uputstvo — ideja rešenja

Ključno posmatranje

• Svaka etiketa t se postavlja tačno jednom, u koraku t, na poziciju idx_t.
• Konačna etiketa na poziciji j je najveći broj t za koji je ta pozicija posećena.
• Ako u konačnom nizu postoji e_j = t, onda etiketa t mora biti postavljena baš na toj poziciji.
• Ako etiketa t ne postoji u nizu e, ona je mogla biti postavljena na bilo koju poziciju gde važi e_j ≥ t (jer će kasnije biti prebrisana većom etiketom).
• Kretanje je uvek lokalno: u svakom koraku pomeramo se za tačno jedno mesto levo ili desno.

Dinamičko programiranje

• Definišemo dp[t][j] = broj načina da se nakon postavljanja etikete t nalazimo na poziciji j.
• Dozvoljene pozicije u koraku t su sve j za koje važi e_j ≥ t.
• Ako postoji pozicija j sa e_j = t, tada je idx_t fiksiran i samo ta pozicija je dozvoljena.

Prelaz

dp[t][j] = dp[t−1][j−1] + dp[t−1][j+1]
  

(naravno, samo ako je pozicija j dozvoljena u koraku t).

Bazni slučaj

• Za t = 1 možemo krenuti sa bilo koje pozicije gde važi e_j ≥ 1.
• Zato je dp[1][j] = 1 za sve takve pozicije.

Konačan odgovor

• Nakon koraka K, sabiramo sve dp[K][j] gde važi e_j ≥ K.

Rešenje (C++)

// Zadatak 6 – Etiketiranje
// Dinamičko programiranje po vremenu (etiketi) i poziciji

#include 
using namespace std;

static const int MOD = 998244353;

inline int addmod(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    // e[i] = konačna etiketa na poziciji i (1-indexirano)
    vector e(N + 2, 0);
    for (int i = 1; i <= N; i++) {
        cin >> e[i];
    }

    // dp_prev[j] = dp[t-1][j], dp_cur[j] = dp[t][j]
    vector dp_prev(N + 2, 0), dp_cur(N + 2, 0);

    // t = 1 (bazni slučaj)
    bool possible = false;
    for (int j = 1; j <= N; j++) {
        if (e[j] >= 1) {
            dp_prev[j] = 1;
            possible = true;
        }
    }

    if (!possible) {
        cout << 0 << "\n";
        return 0;
    }

    // DP po etiketama 2..K
    for (int t = 2; t <= K; t++) {
        fill(dp_cur.begin(), dp_cur.end(), 0);

        int forced_pos = -1;
        for (int j = 1; j <= N; j++) {
            if (e[j] == t) {
                forced_pos = j;
                break;
            }
        }

        if (forced_pos != -1) {
            int j = forced_pos;
            int ways = 0;
            if (j > 1) ways = addmod(ways, dp_prev[j - 1]);
            if (j < N) ways = addmod(ways, dp_prev[j + 1]);
            dp_cur[j] = ways;
        } else {
            for (int j = 1; j <= N; j++) {
                if (e[j] >= t) {
                    int ways = 0;
                    if (j > 1) ways = addmod(ways, dp_prev[j - 1]);
                    if (j < N) ways = addmod(ways, dp_prev[j + 1]);
                    dp_cur[j] = ways;
                }
            }
        }

        dp_prev.swap(dp_cur);
    }

    long long answer = 0;
    for (int j = 1; j <= N; j++) {
        if (e[j] >= K) {
            answer = (answer + dp_prev[j]) % MOD;
        }
    }

    cout << answer << "\n";
    return 0;
}