USP Januar 2 (2026)

Beskonačni hangar

Napisati program koji omogućava kreiranje hangara za galaktičke brodove čiji kapacitet nije ograničen (3 poena). Galaktički brodavi imaju svoj naziv i broj putnika (1 poen). Brodovi se smeštaju u hangar po redosledu njihovog dolaska. Nakon što se svi brodovi smeste u hangar, omogućiti da veličina hangara bude ograničena na broj borodova koji su trenutno smešteni u hangar (1 poen).

Omogućiti da se izračuna ukupan broj putnika koji su pristigli u hangar, kao i da se pronađe naziv broda sa najvećim brojem putnika (1 poen).

Ulaz

Program se pokreće sa jednim argumentom komandne linije koji predstavlja naziv datoteke u kojoj se nalaze informacije o brodovima (1 poen):

./beskonacni_hangar <naziv_datoteke>

U datoteci se nalaze informacije o brodovima. Svaki brod je opisan u zasebnom redu na sledeći način (2 poena):

<naziv_broda> <broj_putnika>

,gde <naziv_broda> predstavlja naziv broda (niz karaktera bez razmaka maksimalne dužine 63), a <broj_putnika> predstavlja broj putnika na brodu (ceo broj).

Izlaz

Na standardni izlaz ispisati ukupan broj putnika koji su pristigli u hangar, kao i naziv broda sa najvećim brojem putnika (1 poen).

U slučaju greške, na standardni izlaz za greške ispisati -1 i prekinuti program sa izlaznim kodom neuspeha (1) (1 poen).

Primer

command line

./beskonacni_hangar brodovi.txt

brodovi.txt

Enterprise 1000
Millennium_Falcon 4
Serenity 5
Nostromo 20
Nebulon_B 200
Ark 50
Odyssey 300
Slipstream 150
Galactus 5000
Hyperion 100
Quantum 10
Titan 2000

stdout

8839
Galactus

Primer

command line

./beskonacni_hangar galakticki_brodovi.txt

stderr

-1

Super Mario

U igri Super Mario, igrač se kreće po mapi i treba da pokupi što više pečuraka pre nego što stigne do cilja. Napisati program koji simulira igru Super Mario korišćenjem dvostruko povezanih listi. Mapa igre je predstavljena u vidu dvostruko povezane liste pri čemu elementi liste označavaju:

• broj 1 označava livadu
• broj 2 označava prepreku
• broj 3 označava pečurku
• broj 4 označava cilj
• broj 5 označava igrača

Program treba da implementira sledeće funkcionalnosti:

• (1 poen) cvor* pronađi_igrača(cvor* sentinel) - funkcija pronalazi igrača u listi i vraća pokazivač na odgovarajući element u listi. U slučaju da igrač ne postoji, funkcija vraća NULL.

• (2.5 poena) int pomeri_ulevo(cvor* sentinel, cvor** igrac) - funkcija pomera igrača jedno mesto ulevo. Ukoliko je na tom mestu bila pečurka, igrač je pojede, njegov ukupan rezultat se uveća za $1$, a na tom mestu ostaje livada. Ukoliko je na tom mestu prepreka ili više njih, igrač ih preskače i završava na prvom mestu koje nije prepreka. Funkcija vraća 1 ukoliko dođe do greške, a 0 inače.

• (2.5 poena) int pomeri_udesno(cvor* sentinel, cvor** igrac) - funkcija pomera igrača jedno mesto udesno. Ukoliko je na tom mestu bila pečurka, igrač je pojede, njegov ukupan rezultat se uveća za $1$, a na tom mestu ostaje livada. Ukoliko je na tom mestu prepreka ili više njih, igrač ih preskače i završava na prvom mestu koje nije prepreka. Funkcija vraća 1 ukoliko dođe do greške, a 0 inače.

• (3 poena) Glavni program koji simulira igru. Sa standardnog ulaza se najpre učitava dvostruko povezana lista koja predstavlja mapu do unosa broja -1. Nakon toga, unose se komande d(desno) ili l(levo) do kraja ulaza koje zadaju na koju stranu će se igrač pomeriti. Nakon svakog pomeranja, ispisati listu. Ukoliko igrač u bilo kom trenutku stigne do cilja, ispisati njegov ukupan broj poena i završiti program. U suprotnom, na standardni izlaz ispisati GAME OVER.

• (1 poen) U slučaju greške, na standardni izlaz za greške ispisati -1 i prekinuti program sa izlaznim kodom neuspeha (1).

Ulaz

Sa standardnog ulaza se najpre učitava dvostruko povezana lista koja predstavlja mapu do unosa broja -1. Nakon toga, unose se komande d(desno) ili l(levo) do kraja ulaza koje zadaju na koju stranu će se igrač pomeriti.

Izlaz

Nakon svakog pomeranja, ispisati listu. Ukoliko igrač u bilo kom trenutku stigne do cilja, ispisati njegov ukupan broj poena i završiti program. U suprotnom, na standardni izlaz ispisati GAME OVER. U slučaju greške, na standardni izlaz za greške ispisati -1 i prekinuti program sa izlaznim kodom neuspeha (1).

Primer

Ulaz

1 2 2 5 2 3 4 1 3 -1
d
l
l
l
d
l
l
l
d

Izlaz

[1, 2, 2, 1, 2, 5, 4, 1, 3]
[1, 2, 2, 5, 2, 1, 4, 1, 3]
[5, 2, 2, 1, 2, 1, 4, 1, 3]
[1, 2, 2, 1, 2, 1, 4, 1, 5]
[5, 2, 2, 1, 2, 1, 4, 1, 1]
[1, 2, 2, 1, 2, 1, 4, 1, 5]
[1, 2, 2, 1, 2, 1, 4, 5, 1]
[1, 2, 2, 1, 2, 1, 5, 1, 1]
2

Primer

Ulaz

1 2 2 5 2 3 4 1 3 -1
d
l
l
l
d
l
l

Izlaz

[1, 2, 2, 1, 2, 5, 4, 1, 3]
[1, 2, 2, 5, 2, 1, 4, 1, 3]
[5, 2, 2, 1, 2, 1, 4, 1, 3]
[1, 2, 2, 1, 2, 1, 4, 1, 5]
[5, 2, 2, 1, 2, 1, 4, 1, 1]
[1, 2, 2, 1, 2, 1, 4, 1, 5]
[1, 2, 2, 1, 2, 1, 4, 5, 1]
GAME OVER

Primer

Ulaz

1 2 2 5 2 3 4 1 3 -1
d
l
l
s
d
l
l
l
d

Izlaz

[1, 2, 2, 1, 2, 5, 4, 1, 3]
[1, 2, 2, 5, 2, 1, 4, 1, 3]
[5, 2, 2, 1, 2, 1, 4, 1, 3]

Izlaz za greške

-1

Binarno pretraživačko stablo

(4 poena) Napisati funkciju void razlika_dece(Cvor *koren) koja ispisuje razliku vrednosti leve i desne dece svakog čvora u prefiksnom obilasku stabla. Ako čvor nema levo ili desno dete, za njihvu vrednost se uzima 0.

(6 poena) Napisati funkciju Cvor *donja_granica(Cvor* koren, int nivo, int x) koja vraća pokazivač na čvor sa najvećom vrednošću koja je manja ili jednaka od x na zadatom nivou nivo. Nivoi stabla se broje od 0. Ako na zadatom nivou ne postoji čvor koji ispunjava uslov, funkcija treba da vrati NULL.

Ulaz

Sa standardnog ulaza se učitava broj čvorova $n$, a zatim i $n$ vrednosti, koje se ubacuju u binarno pretraživačko stablo.

Nakon toga, učitava se jedna od sledećih opcija:

• s: Poziva funkciju razlika_dece koja ispisuje razliku vrednosti leve i desne dece svakog čvora u prefiksnom obilasku stabla.
• t x nivo: Poziva funkciju donja_granica za vrednosti x i nivo i ispisuje rezultat poziva funkcije.

Izlaz

Na standardni izlaz ispisati rezultat poziva funkcije u zavisnosti od opcije. Ukoliko ne postoji čvor koji ispunjava uslov za opciju t, ispisati NEMA.

Primer

Ulaz

6
5 3 2 4 7 8
s

Izlaz

-4
-2
0
0
-8
0

Primer

Ulaz

6
5 3 2 4 7 8
t 5 2 

Izlaz

4

Primer

Ulaz

6
5 3 2 4 7 8
t 1 2 

Izlaz

NEMA

Undo red

Implementirati generičku klasu UndoRed<T> koja implementira red sa undo funkcionalnošću. Klasa treba da podržava sledeće operacije:

• (2 poena) void push(T x): Dodaje element x na kraj reda.
• (2 poena) const T &front() const: Vraća referencu na prvi element reda. Ako je red prazan, onda baca izuzetak std::out_of_range("Red je prazan").
• (2 poena) void pop(): Uklanja prvi element reda. Ako je red prazan, onda baca izuzetak std::out_of_range("Red je prazan"). Nakon operacije pop, undo istorija se briše, tako da se ne može vratiti u stanje pre pop operacije.
• (2 poena) void undo(): Vraća red u stanje pre poslednje operacije push. Ako nije bilo operacije push, funkcija undo ne menja stanje reda.

Implementirati sve funkcije u amortizovanoj vremenskoj složenosti $O(1)$ (2 poena).

Ulaz

Sa standardnog ulaza, sve do kraja ulaza, učitavaju se operacije oblika:

• e x: Dodaje element x na kraj reda.
• f: Ispisuje prvi element reda.
• d: Uklanja prvi element reda.
• u: Poziva funkciju undo.

Izlaz

Na standardni izlaz ispisati rezultat operacije f. Ako je red prazan, za operaciju f i d na standardni izlaz za greške ispisati poruku Red je prazan.

Primer

stdin

e 1
e 2
f
d
f
d
e 3
e 4
f
u
d
f

stdout

1
2
3

stderr

Red je prazan

Objašnjenje

• e 1: Red postaje [1].
• e 2: Red postaje [1, 2].
• f: Ispisuje se 1.
• d: Red postaje [2].
• f: Ispisuje se 2.
• d: Red postaje [].
• e 3: Red postaje [3].
• e 4: Red postaje [3, 4].
• f: Ispisuje se 3.
• u: Red se vraća u stanje pre poslednjeg push, tj. red postaje [3].
• d: Red postaje [].
• f: Red je prazan, ispisuje se poruka Red je prazan na standardni izlaz za greške.

Primer

stdin

e 10
e 20
d
u
f

stdout

20

Objašnjenje

• e 10: Red postaje [10].
• e 20: Red postaje [10, 20].
• d: Red postaje [20].
• u: Red se ne menja jer nije bilo operacije push nakon poslednjeg pop.
• f: Ispisuje se 20.