USP Kolokvijum II (2026)

Putovanje

Neka je dato savršeno binarno stablo koje predstavlja moguću mapu presedanja između gradova, počevši od korena. Svaki čvor stabla sadrži ime grada i cenu karte do tog grada.

Primer takvog stabla:

                    (0, Beograd)
                    /             \
        (120, London)        (50, Budimpesta)
        /           \            /           \
(400, Njujork)  (300, Moskva) (50, Milano)  (80, Lisabon) 

Implementirati sledeće funkcije:

• void izmeni(Stablo koren) - Menja stablo tako da svaki čvor sadrži ukupnu cenu karte do tog grada, počevši od korena (3 poena). Na primer, nakon izmene, stablo iz primera bi izgledalo ovako:

                    (0, Beograd)
                    /             \
        (120, London)        (50, Budimpesta)
        /           \            /           \
(520, Njujork)  (420, Moskva) (100, Milano)  (130, Lisabon)

• Stablo najskuplja_destinacija(Stablo koren) - Pronalazi najskuplju destinaciju (3 poena).

• int ukupna_cena(Stablo koren, char** zelja, const size_t n) - Proverava da li postoji put, počevši od korena, koji prolazi redom kroz sve gradove u nizu zelja dužine ni vraća ukupnu cenu tog puta. Ako takav put ne postoji, funkcija treba da vrati -1 (4 poena).

Ulaz

U datoteci ulaz.txt nalaze se podaci o čvorovima savršenog binarnog stabla zadati u prefiksnom obliku, gde je svaki čvor predstavljen linijom u formatu:

<tip> <cena> <ime_grada>

gde <tip> može biti C (čvor sa decom) ili E (čvor bez dece), a <ime_grada> je maksimalno 10 karaktera.

Nakon učitavanja stabla, sa standardnog ulaza se učitava broj gradova koje korisnik želi da poseti i niz želja, odnosno imena gradova koje korisnik želi da poseti.

Izlaz

Na standardan izlaz se prvo ispisuje stablo nakon izmene funkcijom akomuliraj, zatim se ispisuje najskuplja destinacija i ukupna cena puta kroz željene gradove ili poruka da put ne postoji.

Primer

ulaz.txt

C 0 Beograd
C 120 London
E 400 Njujork
E 300 Moskva
C 50 Budimpesta
E 50 Milano
E 80 Lisabon

stdin

3
Beograd Budimpesta Lisabon

stdout

(520, Njujork)
(120, London)
(420, Moskva)
(0, Beograd)
(100, Milano)
(50, Budimpesta)
(130, Lisabon)
Najskuplja destinacija je: Njujork po ceni od: 520
Mozes ispuniti zelje po ceni od: 130

Primer

ulaz.txt

C 0 Beograd
C 120 London
E 400 Njujork
E 300 Moskva
C 50 Budimpesta
E 50 Milano
E 80 Lisabon

stdin

2
Beograd Amsterdam

stdout

(520, Njujork)
(120, London)
(420, Moskva)
(0, Beograd)
(100, Milano)
(50, Budimpesta)
(130, Lisabon)
Najskuplja destinacija je: Njujork po ceni od: 520
Zelje nisu moguce!

Ograničavač zahteva

Napisati klasu ogranicavac_zahteva koja ograničava broj zahteva koje korisnik može da pošalje u određenom vremenskom periodu. Klasa treba da ima sledeće funkcionalnosti:

• ogranicavac_zahteva(size_t limit, Time vremenski_period) - konstruktor koji postavlja maksimalan broj zahteva u određenom vremenskom periodu.
• bool je_dozvoljeno(const ID id, Time trenutno_vreme) - proverava da li je korisniku sa datim ID-jem dozvoljeno da pošalje zahtev u dato vreme.
• void evidentiraj_zahtev(const ID id, Time trenutno_vreme) - evidentira zahtev korisnika sa datim ID-jem u dato vreme, a ako zahtev nije dozvoljen, baca izuzetak std::runtime_error("Zahtev nije dozvoljen").

Obe funkcije je_dozvoljeno i evidentiraj_zahtev treba da rade u $O(1)$ vremenu.

Napomena: Primetite da se u funkciji evidentiraj_zahtev ne prosleđuje zahtev, već samo ID i trenutno vreme. Ova funkcija treba da evidentira zahtev korisnika, ali ne treba da zna detalje zahteva, sem trenutka kada je zahtev poslat.

Ulaz

Sa standardnog ulaza se učitavaju dva cela broja: $k$ i $t$, gde $k$ predstavlja maksimalan broj zahteva koji korisnik može da pošalje u vremenskom periodu od $t$ jedinica vremena. Nakon toga, sve do kraja ulaza, učitavaju se zahtevi u formatu: ID trenutno_vreme, gde ID predstavlja identifikator korisnika, a trenutno_vreme predstavlja vreme kada je zahtev poslat. Pretpostaviti da će svako sledeće trenutnо_vreme biti veće ili jednako prethodnom.

Izlaz

Na standardni izlaz ispisati poruku Zahtev evidentiran za svaki zahtev koji je uspešno evidentiran, a na standardni izlaz za greške ispisati poruku Zahtev nije dozvoljen za svaki zahtev koji nije dozvoljen.

Primer

stdin

3 10
1 0
1 3
1 7
2 7
2 8
1 9
1 10
2 17
2 18
1 20

stdout

Zahtev evidentiran
Zahtev evidentiran
Zahtev evidentiran
Zahtev evidentiran
Zahtev evidentiran
Zahtev evidentiran
Zahtev evidentiran
Zahtev evidentiran

stderr

Zahtev nije dozvoljen
Zahtev nije dozvoljen

Objašnjenje

• 1 0 - Korisnik 1 šalje zahtev u vreme 0. Dozvoljeno jer nema prethodnih zahteva. (0)
• 1 3 - Korisnik 1 šalje zahtev u vreme 3. Dozvoljeno jer je korisnik 1 poslao samo 1 zahtev u poslednjih 10 jedinica vremena (0-3).
• 1 7 - Korisnik 1 šalje zahtev u vreme 7. Dozvoljeno jer je korisnik 1 poslao samo 2 zahteva u poslednjih 10 jedinica vremena (0-3-7).
• 2 7 - Korisnik 2 šalje zahtev u vreme 7. Dozvoljeno jer nema prethodnih zahteva. (7)
• 2 8 - Korisnik 2 šalje zahtev u vreme 8. Dozvoljeno jer je korisnik 2 poslao samo 1 zahtev u poslednjih 10 jedinica vremena (7-8).
• 1 9 - Korisnik 1 šalje zahtev u vreme 9. Nije dozvoljeno jer je korisnik 1 poslao 3 zahteva u poslednjih 10 jedinica vremena (0-3-7).
• 1 10 - Korisnik 1 šalje zahtev u vreme 10. Nije dozvoljeno jer je korisnik 1 poslao 3 zahteva u poslednjih 10 jedinica vremena (0-3-7).
• 2 17 - Korisnik 2 šalje zahtev u vreme 17. Dozvoljeno jer je korisnik 2 poslao samo 2 zahteva u poslednjih 10 jedinica vremena (7-8-17).
• 2 18 - Korisnik 2 šalje zahtev u vreme 18. Dozvoljeno jer je korisnik 2 poslao samo 2 zahteva u poslednjih 10 jedinica vremena (8-17-18).
• 1 20 - Korisnik 1 šalje zahtev u vreme 20. Dozvoljeno jer je korisnik 1 poslao samo 1 zahteva u poslednjih 10 jedinica vremena (10-20).