USP Januar 1 (2026)

Kupovina

Kupac ima spisak namirnica koje želi da kupi u prodavnici. Na spisku se pored naziva namirnice nalazi i količina koju kupac želi da kupi. Na sajtu prodavnice se nalazi cenovnik na kome su navedene cene namirnica. Kupac želi da sortira namirnice sa svog spiska po ukupnoj ceni nerastuće, a ukoliko su ukupne cene iste leksikografski rastuće. Napisati program koji će pomoći kupcu da ostvari svoj cilj.

Poeni po delovima zadatka:

(1 poen) Predstavljanje namirnica strukturom
(2 poena) Rad sa ulaznim fajlovima i argumentima komandne linije
(2 poena) Alokacija memorije
(1 poen) Funkcija za poređenje namirnica
(2 poena) Sortiranje namirnica i ispis
(1 poen) Obrada greški

Ulaz

Kao argumenti komandne linije se zadaju imena dva fajla. U prvom se nalazi najpre broj namirnica, a zatim i spisak kupca koji u svakom redu sadrži ime namirnice (niska bez belina maksimalne dužine 31) i količinu (ceo broj). U drugom fajlu se nalazi broj artikala u prodavnici, a zatim i cenovnik koji u svakom redu sadrži ime namirnice (niska bez belina maksimalne dužine 31) i cenu (realan broj).

Izlaz

U fajl spisak_sortirano.txt upisati spisak namirnica sortiran po datim kriterijumima. U slučaju greške, na standardni izlaz za greške ispisati -1 i prekinuti program sa izlaznim kodom neuspeha (1).

Primer

`command line`

./a.out spisak.txt cenovnik.txt

`spisak.txt`

5
cokolada 5
sir 1
hleb 3
voda 6
mleko 2

`cenovnik.txt`

7
mleko 85.99
cokolada 250.99
pasteta 70.99
sir 170.98
voda 70.99
hleb 49.99
kecap 139.99

`spisak_formatirano.txt`

cokolada
voda
mleko
sir
hleb

Primer

`command line`

./a.out spisak.txt cenovnik.txt

`spisak.txt`

5
cokolada 5
sir 1
kafa 3
voda 6
mleko 2

`spisak.txt`

7
mleko 85.99
cokolada 250.99
pasteta 70.99
sir 170.98
voda 70.99
hleb 49.99
kecap 139.99

`stderr`

-1

Objašnjenje

Kafa ne postoji na cenovniku.

Sortiranje fajlova

Radnik u gradskoj arhivi želi da sortira fajlove na svom računaru. Za svaki fajl je poznat jedinstven identifikator. Napisati program koji sortira fajlove korišćenjem algoritma insertion sort nad listom. Program treba da implementira sledeće funkcionalnosti:

(1 poen) int ubaci_fajl_iza(cvor *fajl1, cvor *fajl2) - funkcija ubacuje fajl2 iza fajla fajl1 u listi fajlova. Funkcija vraća 1 u slučaju da neki od prosleđenih fajlova ne postoji, a 0 inače.
(2 poena) cvor* nadji_poslednji_manji(cvor *sentinel, cvor *fajl) - funkcija pronalazi i vraća pokazivač na poslednji element liste manji od elementa fajl, a koji se nalazi između elemenata sentinel i fajl. Ukoliko takav element ne postoji, vraća se sentinel. Ukoliko je neki od prosleđenih argumenata nepostojeći, funkcija vraća NULL.
(2 poena) cvor* nadji_poslednji_veci(cvor *sentinel, cvor *fajl) - funkcija pronalazi i vraća pokazivač na poslednji element liste veći od elementa fajl, a koji se nalazi između elemenata sentinel i fajl. Ukoliko takav element ne postoji, vraća se sentinel. Ukoliko je neki od prosleđenih argumenata nepostojeći, funkcija vraća NULL.
(2 poena) int sortiraj_fajlove(cvor *sentinel, char opcija) - funkcija sortira listu fajlova zadatu kao prvi argument implementiranjem algoritma insertion sort. Ukoliko je opcija karakter o, onda sortirati listu opadajuće, a ukoliko je opcija karakter r, onda sortirati listu rastuće. Funkcija vraća 1 ukoliko je došlo do bilo kakve greške, a 0 u suprotnom.
(2 poena) Glavni program u kom se zadaje upit za sortiranje fajlova. Najpre se učitava lista sa identifikatorima fajlova, a zatim i jedan karakter koji zadaje opciju kako sortirati fajlove. Na standardni izlaz ispisati sortiranu listu fajlova.
(1 poen) U slučaju greške, na standardni izlaz za greške ispisati -1 i prekinuti program sa izlaznim kodom neuspeha (1).

Napomena: Zadatak se mora uraditi korišćenjem listi. Algoritam insertion sort funkcioniše na sledeći način:

Krećemo se kroz listu element po element;
Tekući element se ubacuje u deo liste pre njega pri čemu taj deo liste treba da ostane sortiran;
Ovo se postiže tako što se element ubacuje nakon poslednjeg elementa koji je manji (ili veći u slučaju opadajućeg sortiranja) od njega.

Ulaz

Sa standardnog ulaza se učitava lista sa identifikatorima fajlova, a zatim i jedan karakter koji zadaje opciju kako sortirati fajlove:

o - sortirati opadajuće
r - sortirati rastuće

Izlaz

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

Primer

`stdin`

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

`stdout`

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

Primer

`stdin`

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

`stdout`

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

Primer

`stdin`

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

`stderr`

-1

Binarno stablo

Neka je dato stablo koje u svakom čvoru čuva vrednost 0 ili 1. Stablo se kreira tako što se u njega ubacuju binarni brojevi, pri čemu se svaki bit broja koristi za izbor grane (levo za 0, desno za 1) prilikom ubacivanja. Na taj način, svaka putanja od korena do lista je jedan broj u binarnom zapisu. Koren sadrži nevalidnu vrednost (-1) u svom čvoru. Primetiti da se u stablu ne mogu nalaziti duplikati.

Primer stabla u kome se nalaze brojevi 00, 01 i 11:

Implementirati sledeće funkcije:

(3 poena) int svi_parni(Cvor* koren) - Proverava da li su svi brojevi u stablu parni. Vraća 1 ako su svi parni, inače vraća 0.
(3 poena) void ispisi(Cvor* koren) - Ispisati sve brojeve koji se nalaze u stablu, svaki u zasebnom redu. Brojevi treba da budu ispisani rastuće u dekadnom zapisu.
(4 poena) void najpribliznija_negacija(Cvor* koren, const char* broj) - Za dati binarni broj ispisati binarni broj iz stabla koji je najbliži bitovskoj negaciji datog broja. Stablo se obilazi od korena ka listu, pri čemu se na svakom nivou preferira grana koja odgovara negiranom bitu, a ako ona ne postoji bira se alternativna grana. Pretpostaviti da je dužina datog broja jednaka dužini brojeva u stablu.

Ulaz

Sa standardnog ulaza se učitava broj binarnih brojeva $n$, koji se ubaciju u stablo, a zatim i $n$ binarnih brojeva iste dužine. Nakon toga, učitava se jedna od sledećih opcija:

p - poziva funkciju svi_parni
i - poziva funkciju ispisi
n binarni_broj - poziva funkciju najpribliznija_negacija kojoj se prosledjuje učitani binarni_broj

Izlaz

Na standardni izlaz ispisati rezultat poziva funkcije u zavisnosti od opcije. Specijalno, za funkciju svi_parni ispisati DA ukoliko su svi brojevi u stablu parni, a NE inače.

Primer 1

`stdin`

`stdout`

NE

Primer 2

`stdin`

`stdout`

Primer 3

`stdin`

`stdout`

Primer 4

`stdin`

`stdout`

DA

Tekst editor

Napisati klasu tekst_editor koja implementira osnovne funkcionalnosti tekst editora:

(1 poen) void pomeri_levo() - pomera kursor ulevo.
(1 poen) void pomeri_desno() - pomera kursor udesno.
(1 poen) void upisi(char c) - upisuje karakter c na poziciju kursora.
(1 poen) void obrisi() - briše karakter levo od kursora.
(3 poena) std::string tekst() const - vraća trenutni tekst u editoru.

Funkcije pomeri_levo, pomeri_desno, upisi i obrisi treba da rade u vremenskoj složenosti $O(1)$, dok funkcija tekst treba da radi u vremenskoj složenosti $O(n)$, gde je $n$ dužina trenutnog teksta u editoru (3 poena).

Ulaz

Sa standardnog ulaza se, sve do kraja unosa, učitavaju naredbe u formatu:

l - pomera kursor ulevo.
d - pomera kursor udesno.
u c - upisuje karakter c na poziciju kursora.
b - briše karakter levo od kursora.
p - ispisuje trenutni tekst u editoru.

Izlaz

Na standardni izlaz ispisati trenutni tekst u editoru nakon svakeke naredbe p.

Primer

`stdin`

u 1
u 2
u 3
p
l
l
u a
u b
p
d
u c
p
l
b
b
p

`stdout`

123
1ab23
1ab2c3
1ac3