Choose jour language!

---

|

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

Prikaži uputstvo Prikaži rešenje (C++)

Uputstvo za rešavanje — ideje, potrebna znanja i pristupi

Problematika: Interaktivni zadatak u kome odgovori na upite vraćaju ili minimum ili maksimum segmenta [L,R] (nasumično). Cilj je pronaći par (L',R') koji zadovoljava uslove Džokera uz što manji broj upita.

Potrebna znanja

• Razumevanje intervala i segmenata niza.
• Strategije interaktivnih algoritama (binarna pretraga, adaptivni upiti).
• Osnovi verovatnoće i statistike (ponavljanje upita i majority voting).
• Konstrukcija nizova koji omogućavaju razlikovanje segmenata.

Glavne ideje za rešavanje

1. Konstrukcija diskriminativnih nizova: osmisliti niz tako da segment [L,R] proizvodi specifične vrednosti koje se razlikuju od ostatka.
2. Ponovljeni upiti: isti upit poslati više puta i posmatrati većinu odgovora kako bi se ublažio uticaj slučajnog izbora min/max.
3. Binarna lokalizacija: segment se može tražiti postavljanjem granica i testiranjem da li traženi deo pripada levom ili desnom intervalu.
4. Probabilistička verifikacija kandidata: za svaku pretpostavku (l,r) proveriti više puta i prihvatiti kandidata koji najčešće prolazi test.

Praktični saveti

• Počni sa manjim vrednostima N i testiraj strategiju lokalno.
• Kombinuj determinističke testove za sužavanje pretrage sa probabilističkim za potvrdu.
• Ograniči broj upita u skladu sa zadatim limitima.

Savet: Eksperimentiši sa različitim konstrukcijama nizova i brojem ponavljanja kako bi našao balans između tačnosti i broja upita.

Praktično rešenje — primer (C++)

Napomena: Sledeći kod ilustruje osnovnu probabilističku strategiju. Nije optimalan za sve slučajeve, ali daje ideju kako implementirati verifikaciju kandidata pomoću ponovljenih upita.

Copy

// 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;
}

Objašnjenje koda:
– send_query: mesto gde bi u realnom zadatku išla komunikacija sa Džokerom.
– verify_candidate: proverava koliko puta kandidat daje očekivan rezultat.
– main: generiše kandidate i koristi verifikaciju da pronađe tačan par.
Ovaj primer pokazuje osnovni okvir – korisnici treba da dodaju konstrukciju nizova i realne upite.

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.

Prikaži uputstvo Prikaži rešenje (C++)

Uputstvo — ideje za rešavanje i potrebna znanja

Tip problema: dinamično drvo (dodavanje listova, brisanje listova, ažuriranje vrednosti) + upiti o zbiru provizija svih potomaka koji su udaljeni ≤ H nivoa naniže od određenog čvora. H je fiksan za ceo test.

Potrebna znanja

• Osnovne strukture podataka: vektori, liste suseda (children), parent pokazivači.
• Algoritmi na stablima — rad sa roditeljskim i potomcima.
• Fenwick/BIT ili segmentno drvo (ako se koristi Euler-tour pristup za neke varijante).
• Tehnike optimizacije: sqrt-dekompozicija, centroid decomposition, lazy ažuriranja (za napredne varijante).

Mogućnosti rešavanja — osnovne ideje

1. Jednostavan, direktan pristup (pogodan ako je H mali):
   • Za svaki čvor održavamo jedinstvenu vrednost sumInRange[v] = zbir težina svih čvorova koji su ispod v i udaljeni ≤ H (kod v).
   • Kada dodajemo novi čvor u drvo (uvećavamo N), penjem se niz roditelje najviše H puta i za svakog roditelja dodajem novu težinu u sumInRange. Isto važi za promenu težine (dodajem delta) i brisanje (oduzimam).
   • Upit za čvor X tada se odgovara u O(1) vraćanjem sumInRange[X].
   • Kompleksnost: svaka promena (dodavanje, izmena, brisanje) zahteva O(H) koraka; upit O(1). Memorija O(N).
2. Boljka osnovnog pristupa:
   • Ako je H velik (npr. H ≈ N), gore opisani pristup može biti preskup (u vremenu), jer svaka promena zahteva O(H) op-a.
3. Napredne opcije za veliki H / veliki Q:
   • **Centroid decomposition**: za svaki centroid čuvamo koliko težine dolazi iz njegovih podstabala po rastojanju — omogućava odgovore i ažuriranja u ~O(log N · f(H)) gde f(H) zavisi od implementacije (može biti O(log N) / O(H) itd.). Implementacija je kompleksnija i zahteva gradnju centroid stabla nad drvetom.
   • **Sqrt-dekompozicija po dubini**: dele se čvorovi po blokovima dubine i održavaju agregati — kompromis između memorije i brzine.
   • **Euler tour + segmentno drvo** — ako biste mogli da obezbedite da svako podstablo nastaje kao interval (što nije trivijalno u online dodavanju bez ažuriranja tout vrednosti svih predaka), mogli biste održavati skupove po dubini. Ali u ovoj zadatoj dinamici ažuriranje tout zahteva hodanje uz roditelje (opet O(depth)).

Objašnjenje "najpraktičnijeg" algoritma (dostupnog i jednostavnog za implementaciju)

S obzirom na dinamiku zadatka (dodavanje listova sa uslovom T < R, brisanje samo listova i menjanje težina), najjednostavnija i najpouzdanija implementacija koja je laka za razumevanje i primenu je metoda sa održavanjem sumInRange[v].

Osnovna logika:

1. Imamo za svaki čvor parent[v], trenutnu težinu w[v] i polje sumInRange[v].
2. U početku (inicijalna N) popunimo sumInRange tako što se za svaki čvor u njegovu hijerarhiju (do H roditelja) doda njegova težina. To je O(N·H) radno vreme za inicijalizaciju.
3. Kada dodajemo novi čvor r sa težinom C i roditeljem T, napravimo:

   cur = r; for steps = 0..H: sumInRange[cur] += C; cur = parent[cur]; stop if cur == 0

4. Ažuriranje težine je analogno (pronađemo delta = novo − staro i penjem se do H roditelja da dodam delta u njihova sumInRange).
5. Brišući list takođe "oduzmem" njegovu težinu iz sumInRange za sve roditelje do udaljenosti H.
6. Upit za X: direktno vraćamo sumInRange[X] (O(1)). Dakle, optimalizujemo vreme upita, a cena je ažuriranje u O(H).

Analiza performansi

• Vremenska složenost (ova implementacija): inicijalizacija O(N·H); svaka operacija tipa 1/2/3: O(H); upit: O(1).
• Prostorna složenost: O(N) (čuvamo roditelja, težinu i sumInRange po čvoru).
• Primer kada je ovo dovoljno: H mali (npr. H ≤ 3000 i Q ≤ 2e5 — praktično upotrebljivo ako H nije ekstremno veliki). U zadacima gde postoje podzadaci sa malim H (npr. H = 1 ili constant), ovo je odličan izbor.
• Za situacije gde je H veliki (~N) i Q takođe veliko, treba razmotriti centroid ili druge napredne metode (složenije za implementaciju, ali brže u praksi).

Napomena: u nastavku (u delu Rešenje) nalaze se kompletan C++ kod (skeleton + implementacija pristupa sa sumInRange) i komentari radi lakšeg razumevanja.

Rešenje (C++) — implementacija pristupa sa sumInRange

Ovo rešenje čuva za svaki čvor zbir težina svih potomaka udaljenih ≤ H i odgovara na upit u O(1). Ažuriranja (dodavanje / izmena / brisanje) rade u O(H).

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;
}
    

Objašnjenje koda (kratko):

• Čuvamo w[i] — trenutnu težinu čvora i parent[i].
• sumInRange[v] je zbir težina svih čvorova koji se trenutno nalaze u sistemu i koji su potomci v na udaljenost ≤ H.
• Inicijalizacija popunjava sumInRange prolazeći svaki čvor i dodajući njegovu težinu njegovim ancestorima do H koraka.
• Svaka operacija tipa 1/2/3 propagira dodatak ili oduzimanje kroz najviše H roditelja (što garantuje ispravnost sumInRange).
• Upit (t=4) vraća sumInRange[X] u O(1).

Napomene i ograničenja

• Ako je H mnogo velik (npr. H ~ N) i Q veliki, ovaj pristup može biti prespor jer svaka izmena radi O(H) rada. U takvim slučajevima razmotri napredne tehnike iz Uputstva (centroid decomposition, sqrt dekompozicija, itd.).
• Ovaj kod očekuje korektan ulaz kakav je opisan u zadatku (nema dodatnih provera za nepostojeće čvorove osim exists prijema).

---

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
  

Prikaži uputstvo Prikaži rešenje (C++)

Uputstvo i ideje za rešavanje

• Koristi prefiksne sume: prefix[i] = x₁ + x₂ + … + xᵢ.
• Za svaku podsekvencu [l, r] količina boje je prefix[r] - prefix[l-1].
• Za svaku koficu y_j proveri da li je zbir deljiv sa y_j.
• Ukupno ima O(n²) podsekvenci, ali moguće je optimizovati korišćenjem hash mapa.
• Pošto je N ≤ 8000, kvadratno rešenje sa pažljivom implementacijom prolazi.

Rešenje (C++)

Copy

// 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.

Prikaži uputstvo Prikaži rešenje (C++)

Ideje za rešenje

• Problem se rešava dinamičkim programiranjem preko dana.
• Definiši dp[day][currency] = maksimalna količina valute currency na kraju dana day.
• Inicijalno: dp[0][1] = 1 (počinje sa 1 BTC).
• Prelaz: dp[day][j] = max(dp[day][j], dp[day-1][i] * A[day-1][i][j]) za sve i, j.
• Na kraju, odgovor je dp[N][1] (maksimalna količina BTC nakon N dana).
• Koristi double ili long double i formatirani ispis sa setprecision.

Primer rešenja (C++)

Copy

// 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

#	Poeni	Ograničenje
0	0	Samo primeri
1	11	N = 1
2	13	Podmatrice se ne preklapaju
3	32	Σ (c_i − a_i + 1)·(d_i − b_i + 1) ≤ 200000
4	44	Bez dodatnih ograničenja

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 uputstvo Prikaži / sakrij rešenje

Uputstvo — ideja rešenja

• Svako ograničenje nameće uslove ekvivalencije među ćelijama matrice (one moraju imati isti tip mleka).
• Problem se svodi na određivanje broja različitih klasa ekvivalencije nad ćelijama.
• Za svaku klasu možemo samostalno odabrati da li će sadržati mleko A ili B.
• Odgovor je zato 2^(broj_klasa) mod 998244353.
• Implementaciono se koristi DSU (Union-Find) struktura da se spoje ćelije koje moraju biti jednake.

Rešenje (C++)

Copy

// Simetrično punjenje — DSU pristup
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

struct DSU {
    vector<int> p, r;
    DSU(int n): p(n), r(n,1){ iota(p.begin(),p.end(),0); }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    void unite(int a,int b){
        a=find(a); b=find(b);
        if(a!=b){
            if(r[a]<r[b]) swap(a,b);
            p[b]=a; r[a]+=r[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);
    auto id=[&](int i,int j){ return (i-1)*M+(j-1); };
    for(int k=0;k<Q;k++){
        int a,b,c,d; cin>>a>>b>>c>>d;
        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));
            }
        }
        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));
            }
        }
    }
    unordered_set<int> roots;
    for(int i=0;i<total;i++) roots.insert(dsu.find(i));
    long long ans=1, base=2;
    int exp=roots.size();
    while(exp){
        if(exp&1) ans=ans*base%MOD;
        base=base*base%MOD;
        exp>>=1;
    }
    cout<<ans<<"\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 na tu teglu (e_{idx₁} = 1).
2. Za svaku sledeću etiketu t = 2..K bira se novo mesto idx_t tako da je |idx_t − idx_{t−1}| = 1 (pomera se za jedan položaj levo ili desno). Na to mesto postavlja etiketu broj t, zamenjujući postojeću etiketu ako je tegla već imala etiketu.

Denis predlaže krajnju konfiguraciju etiketa e₁, e₂, …, e_N (gde neetiketirane tegle imaju etiketu 0). Pitanje: kolikо različitih procesa (tj. različitih sekvenci idx₁..idx_K) mogu dovesti do zadate konačne konfiguracije? Rezultat treba dati modulo 998244353.

Ulaz

• Prvi red: dva cela broja N i K.
• Drugi red: N celih brojeva e₁ e₂ … e_N (0 ≤ e_i ≤ K).

Izlaz

Ispisati jedan ceo broj: broj mogućih procesa modulo 998244353.

Ograničenja

• 2 ≤ N ≤ 5000
• 1 ≤ K ≤ 10000
• 0 ≤ e_i ≤ K
• Ako su i ≠ j i e_i ≠ 0 i e_j ≠ 0 onda e_i ≠ e_j.
• Zadata konfiguracija je validna (garantovano).

Podzadaci

#	Poeni	Ograničenje
1	13	1 ≤ N,K ≤ 20
2	21	1 ≤ N,K ≤ 200
3	26	1 ≤ N ≤ 2000, 1 ≤ K ≤ 5000
4	40	bez dodatnih ograničenja

Primer 1

stdin
4 9
1 8 9 6

stdout
2
  

Primer 2

stdin
6 16
0 5 16 15 12 11

stdout
18
  

Prikaži uputstvo Prikaži rešenje (C++)

Uputstvo — ideja rešenja

Posmatranje (ključna ideja):

• U procesu etiketa t se postavlja tačno jednom, u trenutku t, na nekoj poziciji idx_t.
• Konačna etiketa na poziciji j, e_j, je maksimum vremena t takvih da je u tom trenutku izabrana ta pozicija.
• Za svako t koje se pojavljuje u nizu e, pozicija idx_t je fiksna. Za ostale vrednosti t može biti bilo koja pozicija gde važi e_j ≥ t.
• Svaki korak mora biti pomak od jedne pozicije (|idx_t − idx_{t−1}| = 1).

Modeliranje kao DP:

• Definišemo S_t = { j | e_j ≥ t }.
• Ako postoji j sa e_j = t, onda S_t = {j}.
• dp_t[j] = broj načina da posle koraka t budemo na poziciji j.
• Prelaz: dp_t[j] = (dp_{t-1}[j-1] + dp_{t-1}[j+1]) mod MOD.
• Bazni slučaj: za t=1, dp_1[j] = 1 za svako j u S_1.

Rešenje (C++)

Copy

// Etiketiranje — DP po vremenu i poziciji
#include 
using namespace std;
using int64 = long long;
const int MOD = 998244353;

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;
    if(!(cin >> N >> K)) return 0;
    vector e(N+2, 0);
    for(int i=1;i<=N;i++) cin >> e[i];

    vector dp_prev(N+2, 0), dp_cur(N+2, 0);

    // t = 1
    bool any = false;
    for(int j=1;j<=N;j++){
        if(e[j] >= 1){ dp_prev[j] = 1; any = true; }
    }
    if(!any){ cout << 0 << '\n'; return 0; }

    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, val = 0;
            if(j-1 >= 1) val = addmod(val, dp_prev[j-1]);
            if(j+1 <= N) val = addmod(val, dp_prev[j+1]);
            dp_cur[j] = val;
        } else {
            for(int j=1;j<=N;j++){
                if(e[j] >= t){
                    int val = 0;
                    if(j-1 >= 1) val = addmod(val, dp_prev[j-1]);
                    if(j+1 <= N) val = addmod(val, dp_prev[j+1]);
                    dp_cur[j] = val;
                }
            }
        }
        dp_prev.swap(dp_cur);
    }

    int64 ans = 0;
    for(int j=1;j<=N;j++){
        if(e[j] >= K) ans = (ans + dp_prev[j]) % MOD;
    }
    cout << ans << "\n";
    return 0;
}
      

---

Prethodno
​|< Priprema za drzavno takmičenje i SIO

---