Choose your language!

---

|

NAPREDNE ALGORITAMSKE TEHNIKE

Gramzivi algoritmi (Greedy)

Nauči kako algoritmi donose lokalno najbolje odluke koje vode do optimalnog globalnog rešenja. Upoznaj strategije, intuiciju, dokaze ispravnosti i primene u takmičarskom programiranju.

⚡ Greedy strategije

□ Optimizacija

□ Takmičarski zadaci

□ Analiza složenosti

Gramzivi algoritmi (eng. greedy algorithms) predstavljaju tehniku koja gradi rešenje korak po korak, uvek birajući najbolju lokalnu odluku u datom trenutku. Glavna filozofija je: uzmi ono što ti se trenutno čini najbolje, bez razmišljanja o tome kako će ta odluka uticati na budućnost, u nadi da će niz takvih izbora dovesti do globalno optimalnog rešenja.

Ideja je jednostavna: jednom doneta odluka se nikada ne preispituje niti se algoritam vraća unazad (nema backtracking-a).

Kako razmišlja gramzivi algoritam?

Gramzivi algoritam u svakom koraku bira ono što trenutno izgleda kao najbolje rešenje.

Ne razmišlja o svim mogućim kombinacijama, već donosi odluku odmah.

• uzima najveći novčić
• bira najkraći sledeći korak
• uzima aktivnost koja se najranije završava

Ideja: "Uzmi najbolje sada — nadaj se da će biti najbolje ukupno"

Slika 1: Vizuelni prikaz gramzivog algoritma za vraćanje 62 dinara kusura, korak po korak.

Primer 1: Postupak i vizuelni primer: Vraćanje kusura

Zamisli da treba da vratiš 62 dinara kusura koristeći što manji broj kovanica (apoeni: 50, 20, 10, 5, 1). Gramzivi algoritam bi sledio ove korake:

• Korak 1: Uzmi najveću moguću kovanicu koja ne prelazi 62. To je 50. (Ostaje: 12)
• Korak 2: Uzmi najveću moguću kovanicu za 12. To je 10. (Ostaje: 2)
• Korak 3: Uzmi najveću moguću kovanicu za 2. To je 1. (Ostaje: 1)
• Korak 4: Uzmi još jednu kovanicu od 1. (Ostaje: 0)

U ovom slučaju, dobili smo optimalno rešenje od ukupno 4 kovanice.

Implementacija: Problem kusura u C++

Ovaj kod koristi gramzivu strategiju: uvek uzima najveću moguću kovanicu dok ne dostigne nulu. Obratite pažnju na komentare koji objašnjavaju svaki korak logike.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void vratiKusur(int iznos) {
    // Skup dostupnih apoena (sortiran od najvećeg ka najmanjem)
    // Gramzivi algoritam uvek počinje od najveće vrednosti
    vector<int> apoeni = {50, 20, 10, 5, 1};
    vector<int> rezultat;

    int preostalo = iznos;

    // Prolazimo kroz svaki apoen
    for (int i = 0; i < apoeni.size(); i++) {
        
        // Dokle god je trenutni apoen manji ili jednak preostalom iznosu
        // mi ga "gramzivo" uzimamo
        while (preostalo >= apoeni[i]) {
            preostalo -= apoeni[i];     // Smanjujemo dug
            rezultat.push_back(apoeni[i]); // Dodajemo novčić u novčanik
        }
    }

    // Ispis rezultata
    if (preostalo == 0) {
        cout << "Kusur za " << iznos << " dinara je: ";
        for (int novcic : rezultat) {
            cout << novcic << " ";
        }
        cout << endl << "Ukupno kovanica: " << rezultat.size() << endl;
    } else {
        // Ovo se dešava ako gramzivi algoritam ne može da reši problem 
        // (npr. ako nemamo kovanicu od 1 dinar, a ostane nam kusur)
        cout << "Greška: Gramzivi algoritam nije mogao da vrati tačan iznos!" << endl;
    }
}

int main() {
    int kusur = 62;
    vratiKusur(kusur);
    return 0;
}
    

Analiza koda: Vremenska složenost ovog rešenja je u najgorem slučaju O(n), gde je n broj različitih apoena, jer moramo proći kroz listu kovanica. Iako je veoma brz, ovaj kod bi za apoene {25, 20, 1} i iznos 40 ispisao pogrešan (ne-optimalan) niz kovanica, što je glavna lekcija o gramzivim metodama.

Važno:

Gramzivi algoritmi ne garantuju uvek optimalno rešenje. Izbor koji izgleda najbolji u datom trenutku može dovesti do lošijeg konačnog rezultata.

Primer gde greedy NE radi:

Imamo novčiće: 1, 3, 4 Treba napraviti iznos 6 Gramzivi pristup: 4 + 1 + 1 = 3 novčića ❌ Optimalno rešenje: 3 + 3 = 2 novčića ✅

Da li je gramzivi pristup uvek ispravan?

Odgovor je: NE. Gramzivi algoritmi su "kratkovidi". Ponekad trenutno najbolji potez može blokirati put do stvarno najboljeg ukupnog rešenja.

Primer neuspeha: Treba vratiti 40 dinara, a dostupni apoeni su 25, 20 i 1.
• Greedy: Uzima 25, pa mu ostaje 15, što mora vratiti sa petnaest jedinica. Ukupno 16 kovanica.
• Optimalno: Dve kovanice od po 20. Ukupno 2 kovanice.

Zašto greedy nekad radi, a nekad ne?

Kao što smo videli, gramzivi algoritam ne daje uvek najbolje rešenje. Da bismo znali kada možemo da ga koristimo, postoje određena pravila.

Ova tehnika daje pouzdane rezultate samo ako problem zadovoljava dva ključna svojstva:

• Svojstvo gramzivog izbora: Globalno optimalno rešenje se može postići pravljenjem lokalno optimalnih izbora.
• Optimalna podstruktura: Optimalno rešenje celog problema sadrži u sebi optimalna rešenja njegovih podproblema.

Primeri gde je greedy uspešan: Odabir aktivnosti, Huffmanovo kodiranje, Dijkstrin algoritam, Kruskalov i Primov algoritam.

Primeri gde greedy obično ne radi: Problem ranca (0/1 Knapsack), Problem trgovačkog putnika (TSP).

Osnovna struktura koda

while (postoji moguća odluka):
    x = izaberi najbolju lokalnu opciju (npr. najveću kovanicu ili najkraći put)
    if (x je izvodljivo):
        dodaj x u rešenje
    ažuriraj preostali deo problema
    

Primer 2: Odabir aktivnosti (Activity Selection)

Cilj je odabrati najveći broj aktivnosti koje se ne preklapaju. Greedy strategija: uvek biraj aktivnost koja se najranije završava.

// Sortiramo po vremenu završetka (a.second)
sort(aktivnosti.begin(), aktivnosti.end(), [](auto &a, auto &b){ return a.second < b.second; });

int poslednji_kraj = -1, broj = 0;
for (auto &a : aktivnosti){
    if (a.first >= poslednji_kraj){
        broj++;
        poslednji_kraj = a.second;
    }
}
    

Logika: Što se ranije jedna aktivnost završi, ostaje nam više prostora za ostale.

Prednosti i mane

Prednosti	Mane
Izuzetno brzi (često linearne složenosti)	Nema garancije za globalni optimum bez dokaza
Jednostavni za implementaciju	Ako pogreši, greška je često drastična
Niski zahtevi za memorijom	Zahteva specifičnu strukturu problema

Zaključak

Gramzivi algoritmi su elegantni i efikasni, ali zahtevaju oprez. Ako lokalni optimum ne garantuje globalni, potrebno je koristiti složenije tehnike poput dinamičkog programiranja.

Napredni greedy: pokrivanje celog alfabeta

U nekim problemima greedy se ne koristi za izbor minimuma ili maksimuma, već za praćenje kompletiranih skupova elemenata.

Tipičan primer je rad sa niskama gde želimo da pratimo koliko puta smo uspeli da "sakupimo" sva slova alfabeta.

Ideja:

• Prolazimo kroz nisku s leva na desno
• Vodimo evidenciju koja su slova viđena
• Kada sakupimo svih K različitih slova → pravimo "reset"
• Broj takvih kompletiranja direktno utiče na rešenje

set = prazan skup
broj_setova = 0

za svaki karakter c u stringu:
    dodaj c u skup

    ako skup sadrži svih K slova:
        broj_setova++
        očisti skup

Ključna ideja: svaki put kada sakupimo svih K slova, znamo da smo "potrošili" jednu kompletnu kombinaciju.

Važna intuicija:

Dok ne sakupimo sva slova, uvek postoji neko "kratko" rešenje koje nedostaje. Tek kada kompletiramo ceo skup, prelazimo na sledeći nivo — zato se rezultat menja tek nakon svakog kompletnog seta.

Ova tehnika se često koristi u zadacima gde se traži:

• minimalna dužina nečega što nedostaje
• broj potrebnih segmenata
• ili analiza pokrivenosti svih mogućih izbora

Savet:

Ne pokušavamo da direktno konstruišemo rešenje, već pratimo koliko puta smo uspeli da pokrijemo ceo skup — iz toga zaključujemo odgovor.

U sledećem primeru videćemo kako se ova ideja koristi za rešavanje konkretnog takmičarskog problema.

Zašto greedy ovde radi?

Možda deluje da je potrebno isprobati sve moguće podnizove, što bi bilo presporo (eksponencijalno).

Međutim, greedy radi jer važi sledeće svojstvo:

• Ako nismo sakupili svih K slova → postoji string dužine 1 koji nije podniz
• Kada prvi put sakupimo svih K slova → svi stringovi dužine 1 postoje
• Kada sakupimo 2 puta → svi stringovi dužine 2 mogu postojati

Drugim rečima:

broj kompletnih prolaza kroz alfabet određuje minimalnu dužinu nepodniza

Zato greedy odluka:

• „sakupljaj dok ne dobiješ svih K slova“

daje globalno optimalno rešenje.

Primer 3: Najmanji neviđeni podniz (Missing Subsequence)

Imamo dugačku nisku (string) S koja se sastoji od slova alfabeta veličine K. Želimo da pronađemo dužinu najkraćeg mogućeg stringa koji nije podniz (ne mora biti uzastopan) niske S.

Ovo je savršen zadatak za napredni greedy pristup sa kompletiranjem skupova: da bi najkraći nedostajući niz bio što duži, moramo "potrošiti" što više kompletnih kombinacija slova.

Lokalna odluka: svaki put kada kompletiramo skup od K različitih slova, taj segment smatramo jednim "nivoom" koji smo prešli. Naše rešenje je broj kompletiranih nivoa plus jedan.

#include <iostream>
#include <string>
#include <set>

using namespace std;

// Funkcija pronalazi minimalnu dužinu podniza koji nedostaje
int duzinaNajkracegNedostajucegPodniza(string text, int K) {
    set<char> vidjenaSlova;
    int kompletiraniSetovi = 0;

    // Greedy: prolazimo kroz tekst s leva na desno
    for (char karakter : text) {
        // Dodajemo karakter u trenutni skup
        vidjenaSlova.insert(karakter);

        // Ključna provera: ako skup sadrži svih K slova alfabeta
        if (vidjenaSlova.size() == K) {
            kompletiraniSetovi++; // Potrošili smo jedan segment
            vidjenaSlova.clear();   // RESET: počinjemo od nule za sledeći sloj
        }
    }

    // Rezultat: broj kompletiranih nivoa + 1.
    // To je najmanja dužina niza za koji ne možemo da garantujemo da postoji.
    return kompletiraniSetovi + 1;
}

int main() {
    // Primer: DNK sekvenca sa K=4 alfabeta (A, G, C, T)
    string text = "AGCTAGGCTACGTCA";
    int K = 4; // A, G, C, T
    
    // Za ovaj tekst:
    // [AGCT] (1), [AGGCTA] (2), [CGT] (nepotpun) -> 2 + 1 = 3
    // Najkraći nedostajući niz je dužine 3 (npr. 'AAA' ili 'GGG')
    cout << duzinaNajkracegNedostajucegPodniza(text, K) << endl; 
    return 0;
}

Analiza: Složenost je $O(N \cdot \log K)$ zbog korišćenja `std::set`, što je izuzetno efikasno. Bez ove greedy logike, problem bi bio eksponencijalan. Slika ispod ilustruje ovaj proces scan-and-reset na dugačkom stringu, pokazujući kako se formiraju kompletirani nivoi.

Slika 2: Vizuelizacija algoritma za najmanji nepodniz (abcbaca, K=3)

Objašnjenje algoritma: Najmanji nepodniz

Zadatak traži da za svaki prefiks stringa pronađemo dužinu najkraćeg stringa koji nije njegov podniz.

Podniz je string koji možemo dobiti brisanjem nekih karaktera, ali uz očuvanje redosleda.

Ključna ideja:

Ne tražimo direktno nepodniz. Umesto toga, pratimo koliko puta smo uspeli da vidimo sva slova abecede.

Kako algoritam radi?

Kroz string prolazimo sleva nadesno i održavamo skup različitih karaktera koje smo videli.

• Dodajemo svako novo slovo u skup
• Kada skup sadrži svih K slova → kompletirali smo jedan "set"
• Tada povećavamo brojač i resetujemo skup

Zašto radimo reset?

Reset znači da počinjemo novo "sakupljanje" svih slova — novi nivo.

Veza sa rezultatom

Ako smo uspeli da kompletiramo C setova, to znači:

• svi podnizovi dužine ≤ C postoje
• ali neki podniz dužine C+1 ne postoji

Zaključak:

Najmanji nepodniz ima dužinu C + 1

Zašto se rezultat menja tek nakon kompletnog seta?

Posmatrajmo konkretno šta se dešava sa nepodnizovima dok prolazimo kroz string.

Primer:

• a → nepodnizovi: b, c → dužina = 1
• ab → nepodniz: c → dužina = 1
• abc → sada imamo sva slova → nepodniz: ba → dužina = 2

Vidimo važan obrazac:

• dok ne vidimo sva slova → uvek postoji nepodniz dužine 1
• kada vidimo sva slova → više ne postoji nepodniz dužine 1

Ključna ideja:

Tek kada sakupimo svih K slova, "trošimo" sve kratke nepodnizove i moramo preći na duže.

Šta se dešava kasnije?

Isti princip se ponavlja:

• nakon prvog seta → prelazimo na dužinu 2
• nakon drugog seta → prelazimo na dužinu 3

Zaključak:

Svaki kompletiran set povećava minimalnu dužinu nepodniza za 1.

Objašnjenje slike (korak po korak)

Posmatrajmo string: abcbaca i K = 3 (slova a, b, c)

Koraci:

• Korak 1: {a} → rezultat = 1
• Korak 2: {a, b} → rezultat = 1
• Korak 3: {a, b, c} → kompletiran set → reset → rezultat = 2
• Korak 4: {b} → rezultat = 2
• Korak 5: {b, a} → rezultat = 2
• Korak 6: {b, a, c} → kompletiran set → reset → rezultat = 3
• Korak 7: {a} → rezultat = 3

Intuicija (najvažnije)

Zamisli da skupljaš sličice:

• kada sakupiš sva slova → završio si jedan nivo
• svaki nivo garantuje da postoje svi podnizovi određene dužine

Broj završenih nivoa određuje koliko su "kratki" svi postojeći podnizovi.

Zašto je algoritam efikasan?

• prolazimo kroz string samo jednom → O(N)
• koristimo niz veličine K → O(K)

Savet:

Ovakav pristup se često koristi kada ne tražimo direktno rešenje, već neku osobinu strukture podataka (ovde: koliko puta imamo sva slova).

Slika 3: Vizuelni prikaz algoritma: string se deli na nivoe (setove) u kojima se pojavljuju sva slova, a broj nivoa određuje dužinu najkraćeg nepodniza.

Kako čitati ovu vizualizaciju?

Na slici je prikazan proces pronalaženja najkraćeg nepodniza za string abcabca kada je K = 3 (slova a, b, c).

String se prolazi sleva nadesno i deli na segmente (nivoe) u kojima se pojavljuju sva slova abecede.

Nivo 1

U prvom delu vidimo karaktere a, b, c. Kada sakupimo sva tri slova, kompletiramo prvi set.

• To znači da svi podnizovi dužine 1 postoje

Nivo 2

Zatim ponovo skupljamo slova: b, a, c. Opet imamo sva slova → kompletiran drugi set.

• Sada znamo da postoje svi podnizovi dužine 2

Nivo 3 (nepotpun)

Na kraju ostaje samo a, što nije dovoljno da se kompletira novi set.

Ključni zaključak:

Ako imamo 2 kompletirana nivoa, to znači da svi podnizovi dužine ≤ 2 postoje.

Zato je najkraći nepodniz dužine 3.

Šta znači nepodniz?

Nepodniz je string koji ne možemo dobiti brisanjem karaktera iz originalnog stringa.

U ovom slučaju, neki string dužine 3 ne postoji kao podniz — i to je odgovor.

Savet:

Umesto da tražimo nepodniz direktno, pratimo koliko puta možemo da sakupimo sva slova.

Rešenje zadatka: Najmanji nepodniz za svaki prefiks

Ovaj problem rešavamo efikasno koristeći ideju "slojeva" (layering).

Prolazimo kroz string i pratimo koje smo karaktere videli. Kada sakupimo svih K različitih slova, kompletirali smo jedan nivo.

Za svaki prefiks odgovor je: broj kompletiranih nivoa + 1

#include 
#include 

using namespace std;

// Niz za praćenje da li smo videli karakter
bool vidjen[26];

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    string S;
    cin >> S;

    int broj_setova = 0;        // koliko puta smo videli svih K slova
    int trenutno_razlicitih = 0; // koliko različitih slova trenutno imamo

    for (int i = 0; i < N; i++) {

        int c = S[i] - 'a'; // pretvaramo slovo u indeks (0 do K-1)

        // Ako ovo slovo još nismo videli u trenutnom "setu"
        if (!vidjen[c]) {
            vidjen[c] = true;
            trenutno_razlicitih++;
        }

        // Ako smo sakupili svih K slova
        if (trenutno_razlicitih == K) {

            broj_setova++; // završili smo jedan nivo

            // resetujemo za sledeći nivo
            trenutno_razlicitih = 0;

            for (int j = 0; j < K; j++) {
                vidjen[j] = false;
            }
        }

        // Rezultat za trenutni prefiks:
        // broj kompletiranih nivoa + 1
        cout << broj_setova + 1;

        if (i != N - 1) cout << " ";
    }

    cout << endl;

    return 0;
}

Objašnjenje kako algoritam radi

Posmatrajmo string: abcbaca i K = 3 (slova a, b, c)

Korak po korak:

• a → {a} → imamo 1 slovo → rezultat = 1
• b → {a, b} → imamo 2 slova → rezultat = 1
• c → {a, b, c} → kompletiran set → reset → rezultat = 2
• b → {b} → rezultat = 2
• a → {b, a} → rezultat = 2
• c → {b, a, c} → kompletiran set → reset → rezultat = 3
• a → {a} → rezultat = 3

Zašto ovo radi?

Kada sakupimo svih K slova, to znači da:

• svi podnizovi dužine 1 postoje
• kombinovanjem više nivoa dobijamo sve dužine do C

Ako imamo C kompletiranih nivoa:

• svi podnizovi dužine ≤ C postoje
• ali neki podniz dužine C+1 ne postoji

Zaključak:

Najkraći nepodniz ima dužinu C + 1

Složenost algoritma

• Vremenska složenost: O(N)
• Memorijska složenost: O(K)

Savet:

Umesto da direktno tražimo nepodniz, posmatramo strukturu stringa i brojimo koliko puta možemo da "pokrijemo" sva slova.

Mini izazov

Imamo aktivnosti sa vremenima: (1,3), (2,5), (4,7), (6,9) Zadatak: Izaberi maksimalan broj aktivnosti koje se ne preklapaju. Pitanje: Koju biraš prvu i zašto?

Greedy optimizacije sa akumulacijom efekata

U ovoj lekciji obrađujemo posebnu klasu problema u kojima se greedy odluka ne vidi odmah, već se mora otkriti kroz analizu kako se efekti sabiraju tokom vremena.

Ovakvi zadaci često izgledaju kao simulacija ili dinamičko programiranje, ali se u suštini svode na pametan izbor akcije po koraku + akumulaciju efekta kroz ceo proces.

Ključna ideja

Umesto da pratimo celu simulaciju korak po korak, posmatramo:

• kako svaka odluka utiče na buduće korake
• kako se efekti sabiraju kroz vreme
• i kako možemo unapred izračunati ukupni doprinos

Na taj način, problem se često može svesti na jednostavnu optimizaciju po koraku.

Vizuelna intuicija — akumulacija efekta

Zamisli sledeći proces kroz vreme:

Potez:   1     2     3     4     5
         |-----|-----|-----|-----|

Otrov:   +2    +2    +2    +2    +2
         (akumulira se kroz sve naredne poteze)

Direktni napad: utiče samo u trenutnom potezu

□ Ključna ideja:

• otrov ima trajni efekat
• direktni napad ima trenutni efekat
• zato odluka nije lokalna, već vremenski zavisna

Kako izgleda “naivna” simulacija

za svaki potez:
    izračunaj trenutnu štetu
    dodaj nove efekte
    ponovo prolazi kroz sve prethodne otrove

❌ Ovo je presporo jer stalno ponavljamo iste sabirke.

Kako razmišljamo efikasno

Umesto simulacije, posmatramo:

• ukupan doprinos svakog poteza unapred
• koliko svaki izbor “vredi” na globalnom nivou

To vodi do sledeće transformacije:

• problem iz vremenske simulacije → problem sabiranja doprinosa

Veza sa dinamičkim programiranjem

Iako rešenje izgleda kao greedy, u pozadini postoji DP ideja:

• razmatramo optimalan rezultat za prvih k poteza
• svaki korak zavisi od prethodnih odluka

Međutim, DP tabelu ne moramo eksplicitno da čuvamo jer:

• stanje se može “sažeti” u kumulativne vrednosti
• prelazi se zamenjuju matematičkom formulom

□ Ovo je čest obrazac u takmičarskim zadacima: DP ideja → optimizovana u greedy/matematičko rešenje

Mini intuicija za učenike

Zapamti sledeće pravilo:

• Ako efekat jedne odluke traje kroz više koraka → ne možeš gledati samo trenutni potez
• Ako se efekti sabiraju → probaj da ih “izvučeš ispred petlji”
• Ako vidiš simulaciju → pitaj se da li postoji formula umesto nje

Tipični obrasci ovog tipa problema

• otrov / efekti kroz vreme
• buff/debuff sistemi u igrama
• kumulativni doprinos odluka
• offline izračunavanje rezultata

Zaključak

Greedy algoritmi u naprednim zadacima nisu samo “biraj najbolje sada”, već:

pretvori problem tako da se globalni efekat može izračunati lokalnim odlukama

Upravo u tome leži razlika između osnovnih i takmičarskih greedy problema.

Zadaci za samostalan rad

Ova sekcija sadrži zadatke koji su namenjeni vežbanju i produbljivanju razumevanja obrađenih algoritamskih tehnika. Preporuka je da pokušate da ih rešite bez gledanja u rešenje, jer se upravo kroz samostalni rad razvija algoritamsko razmišljanje.

Zadaci obuhvataju različite nivoe težine — od osnovnog razumevanja greedy pristupa do naprednih problema koji zahtevaju analizu i kombinovanje više ideja.

Slika 3: Vizuelni prikaz greedy algoritma u borbi sa boss-om — “otrov” se akumulira kroz vremensku liniju poteza, dok direktni napadi imaju trenutni efekat. Broj aktivnih efekata određuje ukupnu štetu kroz vreme.

Zadatak 1: Starući prsten — minimalan broj poteza

Igrate najnoviji nastavak popularne igrice "Starući prsten". Poznato je da u ovoj igrici postoji Q šefova, od kojih i-ti ima H_i zdravstvenih poena. Da biste završili igricu, morate da pobedite svakog od njih.

Borba sa svakim šefom traje najviše N poteza. Svaki šef se bori kroz istih N poteza. Tokom k-tog poteza na raspolaganju su dve opcije:

• Direktan napad — šefu se odmah smanjuje broj zdravstvenih poena za Dk.
• Napad sa otrovom — od tog poteza pa nadalje, šefu se nakon svakog narednog poteza, uključujući i trenutni, smanjuje broj zdravstvenih poena za Pk.

Napadi sa otrovom se akumuliraju, pa nakon kraja svakog poteza šef gubi ukupnu sumu svih aktiviranih otrova do tog trenutka.

Ako nakon završetka nekog poteza šef ima najviše 0 zdravstvenih poena, on je pobеđen i borba prestaje.

Potrebno je za svakog šefa ispisati koliko je najmanje poteza potrebno da bi bio pobеđen. Ako nije moguće pobediti šefa nakon najviše N poteza, ispisati -1.

Prikaži / sakrij uputstvo

Uputstvo — kako razmišljati

Na prvi pogled deluje da treba za svakog šefa posebno da simuliramo svih N poteza i da pratimo kako se menjaju zdravstveni poeni.

To bi bilo previše sporo, jer su i N i Q veliki. Zato je potrebno da problem preformulišemo.

---

Ključna ideja

Posmatrajmo jedan fiksan trenutak t. Pitamo se:

Koliku maksimalnu štetu možemo naneti šefu nakon tačno t poteza?

Za svaki potez k imamo dve mogućnosti:

• direktan napad daje Dk štete odmah
• otrov daje Pk štete na svakom potezu od k do t

Ako u potezu k izaberemo otrov, onda njegov ukupni doprinos do trenutka t iznosi:

P[k] * (t - k + 1)

Ako bismo u tom potezu umesto otrova izabrali direktan napad, dobili bismo:

D[k]

Zato je dodatni doprinos otrova u odnosu na direktan napad:

P[k] * (t - k + 1) - D[k]

To možemo preurediti u linearnu formu:

P[k] * t - (P[k] * (k - 1) + D[k])

Dakle, za svaki potez možemo unapred da izračunamo:

• A = P[k]
• B = P[k] * (k - 1) + D[k]

i tada je dodatni doprinos jednak:

A * t - B

---

Vizuelna intuicija

Zamisli sledeći potez:

k-ti potez:

Direktan napad:  D[k]       (daje štetu samo jednom)
Otrov:           P[k]       (daje štetu na svakom potezu do kraja)

Ako gledamo t poteza unapred:

potez k → potez k+1 → potez k+2 → ... → potez t
   +P          +P          +P                +P

Drugim rečima, otrov se ponaša kao trajni efekat, dok je direktan napad jednokratan.

---

Prag isplativosti

Ako je:

A * t - B >= 0

onda se otrov isplati više od direktnog napada. To se dešava kada je:

t >= B / A

Zato svaki potez sa otrovom posmatramo kao kandidata koji postaje koristan tek od nekog trenutka nadalje.

Ako je P[k] = 0, taj potez nikada nije koristan kao otrov.

---

Kako ubrzavamo računanje?

Za sve poteze koji su trenutno isplativi, sabiramo:

• A — zbir svih aktivnih otrova
• B — zbir njihovih konstanti

Tada je dodatna šteta za dati broj poteza t jednaka:

t * suma_A - suma_B

A ukupna šteta nakon t poteza je:

prefiks_direktan[t] + dodatna_steta

gde je prefiks_direktan[t] zbir direktnih napada za prvih t poteza.

---

Veza sa DP idejom

Ovaj zadatak može da izgleda kao da traži dinamiku po potezima, jer posmatramo šta se dešava nakon prvih t koraka. Međutim, umesto klasične DP tabele, uspevamo da ceo problem svedemo na:

• preprocesiranje poteza
• računanje ukupne štete za svaki t
• binarnu pretragu odgovora za svakog šefa

To je tipičan primer zadatka koji liči na DP, ali se elegantnije rešava greedy analizom doprinosa i prefiksnim sumama.

---

Koraci algoritma

• učitati sve poteze
• izračunati prefiksnu sumu direktnih napada
• za svaki potez izračunati kada postaje isplativ kao otrov
• sortirati kandidate po pragu isplativosti
• za svako t = 1..N izračunati maksimalnu štetu
• za svakog šefa binarnom pretragom naći najmanji broj poteza

---

Složenost

Sortiranje kandidata traje O(N log N), a zatim se za svako t računa maksimalna šteta u linearnom prolazu. Za svakog šefa odgovor se nalazi binarnom pretragom.

Ukupna složenost:

O(N log N + Q log N)

Prikaži rešenje

⚠ Pre nego što pogledaš rešenje, pokušaj samostalno!

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

using ll = long long;

/*
    Struktura koja opisuje jedan potez ako ga posmatramo kao "kandidata za otrov".
    Za svaki potez k računamo:
      A = P[k]
      B = P[k] * (k - 1) + D[k]

    Tada je dodatni doprinos otrova za t poteza:
      A * t - B

    Prag govori od kog t taj potez postaje isplativ kao otrov.
*/
struct Potez {
    ll A;       // P[k] - koliko štete daje otrov u jednom potezu
    ll B;       // P[k]*(k-1) + D[k] - konstanta u linearnoj formuli
    double prag; // trenutak kada postaje isplativ: t >= B/A
};

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

    int broj_poteza, broj_sefova;
    cin >> broj_poteza >> broj_sefova;

    // D[k] = šteta direktnog napada u k-tom potezu
    // P[k] = šteta otrova u k-tom potezu
    vector<ll> direktan(broj_poteza + 1);
    vector<ll> otrov(broj_poteza + 1);

    for (int i = 1; i <= broj_poteza; i++) {
        cin >> direktan[i] >> otrov[i];
    }

    /*
        Prefiks suma direktnih napada:

        prefiks_direktan[t] = D[1] + D[2] + ... + D[t]

        Ovo je šteta koju bismo napravili kada bismo
        u svih prvih t poteza birali samo direktan napad.
    */
    vector<ll> prefiks_direktan(broj_poteza + 1, 0);
    for (int i = 1; i <= broj_poteza; i++) {
        prefiks_direktan[i] = prefiks_direktan[i - 1] + direktan[i];
    }

    /*
        Pravimo listu poteza koji mogu biti korisni kao otrov.
        Ako je P[k] = 0, taj potez nikada ne pomaže kao otrov,
        pa ga preskačemo.
    */
    vector<Potez> kandidati;

    for (int k = 1; k <= broj_poteza; k++) {
        if (otrov[k] == 0) continue;

        ll A = otrov[k];
        ll B = otrov[k] * (k - 1) + direktan[k];

        // prag od kog je otrov isplativiji od direktnog napada
        double prag = (double)B / A;

        kandidati.push_back({A, B, prag});
    }

    /*
        Sortiramo po pragu.
        Kako t raste, neki potezi postaju "aktivni",
        tj. isplati se da se računaju kao otrov.
    */
    sort(kandidati.begin(), kandidati.end(), [](const Potez &a, const Potez &b) {
        return a.prag < b.prag;
    });

    /*
        max_steta[t] = maksimalna šteta koju možemo naneti nakon tačno t poteza.
        Kasnije ćemo ovu vrednost učiniti monotonom,
        jer ako već možemo pobediti šefa za t poteza,
        onda svakako možemo i za više.
    */
    vector<ll> max_steta(broj_poteza + 1, 0);

    ll suma_A = 0; // zbir P[k] za sve trenutno aktivne otrove
    ll suma_B = 0; // zbir P[k]*(k-1) + D[k] za sve aktivne otrove

    int pokazivac = 0;

    /*
        Prolazimo kroz broj poteza t = 1..N.
        Za svako t dodajemo sve kandidate koji su postali isplativi.
    */
    for (int t = 1; t <= broj_poteza; t++) {

        while (pokazivac < (int)kandidati.size() && kandidati[pokazivac].prag <= t) {
            suma_A += kandidati[pokazivac].A;
            suma_B += kandidati[pokazivac].B;
            pokazivac++;
        }

        /*
            Dodatna šteta od svih aktivnih otrova:

              Σ (A[k] * t - B[k])
            = t * Σ A[k] - Σ B[k]

            Zato ovde koristimo suma_A i suma_B.
        */
        ll dodatna_steta = suma_A * t - suma_B;

        /*
            Ukupna šteta nakon t poteza:
            - svi direktni napadi za prvih t poteza
            - plus dodatak od svih aktivnih otrova
        */
        max_steta[t] = prefiks_direktan[t] + dodatna_steta;
    }

    /*
        Uređujemo niz tako da bude monoton:
        ako možemo da pobedimo šefa za t poteza,
        onda možemo i za svaki veći broj poteza.
    */
    for (int i = 1; i <= broj_poteza; i++) {
        max_steta[i] = max(max_steta[i], max_steta[i - 1]);
    }

    /*
        Za svakog šefa tražimo najmanji t takav da:
            max_steta[t] >= zdravlje
        To radimo binarnom pretragom.
    */
    while (broj_sefova--) {
        ll zdravlje;
        cin >> zdravlje;

        int levo = 1, desno = broj_poteza;
        int odgovor = -1;

        while (levo <= desno) {
            int sredina = (levo + desno) / 2;

            if (max_steta[sredina] >= zdravlje) {
                odgovor = sredina;
                desno = sredina - 1;
            } else {
                levo = sredina + 1;
            }
        }

        cout << odgovor << '\n';
    }

    return 0;
}

Objašnjenje rešenja

Za svaki broj poteza t unapred računamo maksimalnu štetu koju možemo da nanesemo. To znači da za svaki potez odlučujemo da li je bolje:

• uzeti direktan napad u tom potezu
• ili aktivirati otrov koji od tog poteza pa nadalje pravi veću ukupnu štetu

Pošto je doprinos otrova linearan u t, dovoljno je da za svaki potez znamo:

• od kog trenutka postaje isplativ
• koliko ukupno doprinosi kada je aktivan

Tada ceo zadatak postaje:

• preprocesiranje kandidata
• računanje maksimalne štete za svaki broj poteza
• binarna pretraga odgovora za svakog šefa

---

Zašto je ovo efikasno?

Ne simuliramo svaku borbu posebno. Umesto toga, jednom izračunamo koliko štete možemo napraviti za 1, 2, 3, ..., N poteza. Posle toga za svakog šefa samo tražimo prvi trenutak kada je ta šteta dovoljna.

Zbog toga rešenje radi brzo i prolazi sve testove.

---

Mini intuicija za učenike

Zapamti sledeću ideju:

• direktan napad daje trenutni efekat
• otrov daje efekat koji raste kroz vreme
• zato je važno gledati kako se odluka ponaša za veći broj poteza, a ne samo trenutno

Ovo je baš tip problema gde se na prvi pogled očekuje simulacija, ali se uz dobru analizu dobija mnogo brže rešenje.

---