SORTIRANJE NIZOVA - PRIMERI
1. Uređivanje bašte
Marko je imao bastu sa N saksija cveća poređanih u red od najnize biljke do najvise. Neko vreme je prošlo i pošto biljke rastu različitim brzinama, Marko je primetio da mu bašta više nije uređena. Marko želi ponovo da sredi svoju baštu, a to radi tako što uporedi dve susedne biljke i ako je prva viša od druge, zameni ih. Napisati program koji ispisuje visine biljki u ponovo uređenoj Markovoj bašti.
Ulaz
Broj biljaka N.
N redova sa po jednim brojem koji predstavlja visinu biljke.
Izlaz
N redova sa po jednim brojem koji predstavlja visinu biljke.
Ograničenja
0 ≤ N ≤ 1000, N je ceo broj. Visine biljaka su celi brojevi.
0 ≤ N ≤ 1000, N je ceo broj. Visine biljaka su celi brojevi.
Primer
Ulaz5 4 3 7 8 1
Izlaz
1 3 4 7 8
Ulaz
Broj biljaka N.
N redova sa po jednim brojem koji predstavlja visinu biljke.
Izlaz
N redova sa po jednim brojem koji predstavlja visinu biljke.
Ograničenja
0 ≤ N ≤ 1000, N je ceo broj. Visine biljaka su celi brojevi.
0 ≤ N ≤ 1000, N je ceo broj. Visine biljaka su celi brojevi.
Primer
Ulaz5 4 3 7 8 1
Izlaz
1 3 4 7 8
2. Najkraća ograda
U šumi postoji n vrsta stabala. Za svako od m stabala je data njegova vrsta i geografske koordinate. Šumar hoće da ogradi sva stabla jedne vrste žičanom ogradom pravougaonog oblika (gledano odozgo) čije ivice imaju pravac sever-jug i istok-zapad. Kakvu ogradu treba da napravi tako da potroši najmanje žice?
Ulaz
U prvom redu broj vrsta n i broj stabala m, razdvojeni razmakom. U svakom od sledećih m redova opis jednog stabla: x-koordinata, zatim y-koordinata, i na kraju indeks vrste, razdvojeni razmacima.
Izlaz
U prvom redu indeks ograđene vrste. U drugom redu četiri cela broja razdvojena razmacima koja predstavljaju koordinate temena ograde najmanjeg obima koja obuhvata sva stabla te vrste: najpre x i y koordinata donjeg levog temena, zatim x i y koordinata gornjeg desnog temena (I kvadrant). Ako ima više vrsta koje se mogu ograditi ogradom iste dužine, rešenje je ona sa najmanjim indeksom
Ograničenja
1 ≤ n ≤ 500, 1 ≤ m ≤ 5000. Koordinate su celi brojevi u zatvorenom intervalu između 0 i 1000. Dva stabla mogu imati iste koordinate. Svaka vrsta mora biti zastupljena bar jednim stablom, dakle m ≥ n.
Primer
Ulaz2 5
3 1 0
5 2 0
4 2 1
0 4 0
6 0 1
Izlaz
1
4 0 6 2
U prvom redu broj vrsta n i broj stabala m, razdvojeni razmakom. U svakom od sledećih m redova opis jednog stabla: x-koordinata, zatim y-koordinata, i na kraju indeks vrste, razdvojeni razmacima.
Izlaz
U prvom redu indeks ograđene vrste. U drugom redu četiri cela broja razdvojena razmacima koja predstavljaju koordinate temena ograde najmanjeg obima koja obuhvata sva stabla te vrste: najpre x i y koordinata donjeg levog temena, zatim x i y koordinata gornjeg desnog temena (I kvadrant). Ako ima više vrsta koje se mogu ograditi ogradom iste dužine, rešenje je ona sa najmanjim indeksom
Ograničenja
1 ≤ n ≤ 500, 1 ≤ m ≤ 5000. Koordinate su celi brojevi u zatvorenom intervalu između 0 i 1000. Dva stabla mogu imati iste koordinate. Svaka vrsta mora biti zastupljena bar jednim stablom, dakle m ≥ n.
Primer
Ulaz2 5
3 1 0
5 2 0
4 2 1
0 4 0
6 0 1
Izlaz
1
4 0 6 2
3. Sortiranje brojeva
Napiši program koji uređuje (sortira) niz brojeva neopadajuće (svaki naredni mora da bude veći ili jednak od prethodnog).
Ulaz
Sa standardnog ulaza se unosi broj n (1≤n≤5⋅10^4) a zatim i n prirodnih brojeva manjih od 2n, svaki u posebnom redu.
Izlaz
Na standardni izlaz ispisati učitane brojeve u sortiranom redosledu.
Primer
Ulaz
5 3 1 6 8 1
Izlaz
1 1 3 6 8
Ulaz
Sa standardnog ulaza se unosi broj n (1≤n≤5⋅10^4) a zatim i n prirodnih brojeva manjih od 2n, svaki u posebnom redu.
Izlaz
Na standardni izlaz ispisati učitane brojeve u sortiranom redosledu.
Primer
Ulaz
5 3 1 6 8 1
Izlaz
1 1 3 6 8
4.Najvredniji predmeti
Za svaki predmet koji je na prodaju data je šifra i cena. Kupac ima na raspolaganju određeni iznos dinara i želi da kupi što skuplje predmete. Redom uzima predmete počev od najskupljeg, dok ima novca. Ako nema novca za najskuplji, uzima najskuplji za koji ima novca. Prikazati šifre predmeta koje kupac kupuje i, ako mu je ostalo, preostali iznos novca. Napomena: ova strategija ne garantuje da će predmeti koje kupi biti ukupno najveće moguće vrednosti (npr. ako ima 5 dinara i ako su cene predmeta 4, 3 i 2 dinara, on će kupiti predmet samo predmet od 4 dinara, a mogao bi da kupi predmete od 3 i 2 dinara).
Ulaz
U prvoj liniji standardnog ulaza nalazi se iznos novca (realan broj) koji ima kupac, u drugoj broj predmeta, NN
Izlaz
U svakoj liniji standarnog izlaza ispisuju se šifre i cene kupljenih predmeta (razdvojene razmakom), ako ih ima. U poslednjoj liniji prikazuje se preostali iznos novca, ako postoji.
Primer1
Ulaz
1250.75
5
predmet1
1010.30
predmet2
357.35
predmet3
725.45
predmet4
1125.5
predmet5
115.75
Izlaz
predmet4 1125.5
predmet5 115.75
9.50
Primer2
Ulaz
10000
6
predmet1
3010
predmet2
3005
predmet3
5725
predmet4
1265
predmet5
2075
predmet6
385
Izlaz
predmet3 5725.00
predmet1 3010.00
predmet4 1265.00
Primer3
Ulaz
1000
6
predmet1
3010
predmet2
3005
predmet3
5725
predmet4
1265
predmet5
2075
predmet6
3850
Izlaz
1000.00
U prvoj liniji standardnog ulaza nalazi se iznos novca (realan broj) koji ima kupac, u drugoj broj predmeta, NN
Izlaz
U svakoj liniji standarnog izlaza ispisuju se šifre i cene kupljenih predmeta (razdvojene razmakom), ako ih ima. U poslednjoj liniji prikazuje se preostali iznos novca, ako postoji.
Primer1
Ulaz
1250.75
5
predmet1
1010.30
predmet2
357.35
predmet3
725.45
predmet4
1125.5
predmet5
115.75
Izlaz
predmet4 1125.5
predmet5 115.75
9.50
Primer2
Ulaz
10000
6
predmet1
3010
predmet2
3005
predmet3
5725
predmet4
1265
predmet5
2075
predmet6
385
Izlaz
predmet3 5725.00
predmet1 3010.00
predmet4 1265.00
Primer3
Ulaz
1000
6
predmet1
3010
predmet2
3005
predmet3
5725
predmet4
1265
predmet5
2075
predmet6
3850
Izlaz
1000.00
5.Objedinjavanje
U školi malih žutih mrava nastavnik je pregledao kontrolni zadatak. Prvo je pregledao đake koji su radili grupu A, a zatim one koji su radili grupu B, sredio je rezultate za svaku grupu i mrave poređao na osnovu broja poena koji su osvojili. Napiši program koji mu pomaže da od uređenog spiska učenika koji su radili zadatke iz grupe A i od uređenog spiska učenika koji su radili zadatke iz grupe B dobije jedinstven uređen spisak svih učenika.
Ulaz
Sa standardnog ulaza se unosi broj đaka mm koji su radili grupu A (5≤m≤25000), a zatim neopadajuće sortiran niz poena tih đaka, svaki u posebnoj liniji. Nakon toga se unosi broj n đaka koji su radili grupu B (5≤n≤25000), a zatim neopadajuće sortiran niz poena tih đaka, svaki u posebnoj liniji.
Izlaz
Na standardni izlaz ispisati neopadajuće sortirani niz poena svih đaka zajedno, svaki u posebnoj liniji.
Primer
Ulaz
4 1 3 5 7 3 2 4 5
Izlaz
1 2 3 4 5 5 7
Sa standardnog ulaza se unosi broj đaka mm koji su radili grupu A (5≤m≤25000), a zatim neopadajuće sortiran niz poena tih đaka, svaki u posebnoj liniji. Nakon toga se unosi broj n đaka koji su radili grupu B (5≤n≤25000), a zatim neopadajuće sortiran niz poena tih đaka, svaki u posebnoj liniji.
Izlaz
Na standardni izlaz ispisati neopadajuće sortirani niz poena svih đaka zajedno, svaki u posebnoj liniji.
Primer
Ulaz
4 1 3 5 7 3 2 4 5
Izlaz
1 2 3 4 5 5 7
6.Kružne zone
Kvalitet signala zavisi od udaljenosti tačke od predajnika. Prostor je podeljen u zone oblika kružnih prstenova, pri čemu su širine prstenova međusobno različite. Napiši program koji za datu tačku određuje zonu kojoj pripada.
Ulaz
Sa standardnog ulaza unosi se broj n (1≤n≤50000), a zatim i n realnih brojeva zaokruženih na dve decimale, svaki u posebnom redu, koji predstavljaju širine svih kružnih prstenova. Nakon toga se unosi broj m (1≤m≤50000) i zatim m parova koordinata tačaka (u svakom redu se nalaze dva realana broja zaokružena na dve decimale, razdvojena sa po jednim razmakom).
Izlaz
Na standardni izlaz ispisati m linija. U svakoj liniji ispisati ili indeks zone (broje se od nule) kojoj tačka pripada ili tekst izvan ako je tačka izvan poslednje zone. Ako je tačka na granici dve zone, smatrati da pripada unutrašnjoj.
Primer
Ulaz
3
2.0
3.0
7.0
5
1.0 1.0
2.0 3.0
8.0 7.0
13.2 14.5
0.0 12.0
Izlaz
0
1
2
izvan
2
Sa standardnog ulaza unosi se broj n (1≤n≤50000), a zatim i n realnih brojeva zaokruženih na dve decimale, svaki u posebnom redu, koji predstavljaju širine svih kružnih prstenova. Nakon toga se unosi broj m (1≤m≤50000) i zatim m parova koordinata tačaka (u svakom redu se nalaze dva realana broja zaokružena na dve decimale, razdvojena sa po jednim razmakom).
Izlaz
Na standardni izlaz ispisati m linija. U svakoj liniji ispisati ili indeks zone (broje se od nule) kojoj tačka pripada ili tekst izvan ako je tačka izvan poslednje zone. Ako je tačka na granici dve zone, smatrati da pripada unutrašnjoj.
Primer
Ulaz
3
2.0
3.0
7.0
5
1.0 1.0
2.0 3.0
8.0 7.0
13.2 14.5
0.0 12.0
Izlaz
0
1
2
izvan
2
7.Binarna pretraga
U prodavnici se nalazi puno vrsta proizvoda i poznati su njihovi bar-kodovi. Proizvođač želi da sazna koliko se vrsta njegovih proizvoda prodaje u toj prodavnici. Ako je spisak svih kodova proizvoda u prodavnici dat u sortiranom obliku, a spisak svih kodova proizvoda proizvođača je dostavljen nesortiran, napiši program koji određuje traženi broj.
Ulaz
Sa standardnog ulaza učitava se broj n (1≤n≤50000), a zatim u narednih n linija po jedan prirodan broj (najviše šestocifren). Ti brojevi predstavljaju bar-kodove proizvoda u prodavnici i sortirani su rastuće. Nakon toga se do kraja ulaza učitavaju bar-kodovi proizvoda koje je proizvođač dostavio (najviše šestocifreni prirodni brojevi, svaki u posebnom redu).
Izlaz
Na stanadrni izlaz ispisati broj proizvoda proizvođača koji se već prodaju u prodavnici.
Primer
Ulaz
5
1
3
5
6
7
2
3
4
5
8
Izlaz
2
Sa standardnog ulaza učitava se broj n (1≤n≤50000), a zatim u narednih n linija po jedan prirodan broj (najviše šestocifren). Ti brojevi predstavljaju bar-kodove proizvoda u prodavnici i sortirani su rastuće. Nakon toga se do kraja ulaza učitavaju bar-kodovi proizvoda koje je proizvođač dostavio (najviše šestocifreni prirodni brojevi, svaki u posebnom redu).
Izlaz
Na stanadrni izlaz ispisati broj proizvoda proizvođača koji se već prodaju u prodavnici.
Primer
Ulaz
5
1
3
5
6
7
2
3
4
5
8
Izlaz
2