Županijska razina / Primjena algoritama OŠ 2021. / Osnovna škola (8. razred) - 2. zadatak

Osim što voli sastavljati zadatke za natjecanja, Stjepan je i strastveni kolekcionar čarapa.

Ako ste do sada mislili da je Stjepan čudan, što ćete tek misliti kad čujete da su sve čarape koje posjeduje jednobojne crne! Stjepan u ormaru ima N crnih čarapa raznih veličina.

Čarape razlikujemo samo po veličini.

Jednog dana Stjepanova mama ljutito je uzviknula: “Sad bi bilo dosta! Ako će se sutra, od čarapa iz tvog ormara moći složiti više od K parova čarapa, nagrabusio si!.”

Stjepan je u očaju jer je shvatio da će se morati riješiti nekih čarapa.

Ipak primjetio je da se majka nespretno izrazila i da će možda moći zadržati i neke čarape koje neće imati para.

Pomozi Stjepanu i napiši program koji će odrediti koliko najviše čarapa Stjepan smije zadržati kako ne bi prekršio majčinu zapovijed.

Dvije čarape se mogu upariti ako su iste veličine.

Ulazni podaci

U prvom su retku prirodni brojevi N i K (1 ≤ N, K ≤ 1000), brojevi iz teksta zadatka.

U sljedećem retku je N brojeva koji predstavljaju veličine čarapa. Veličina svake čarape je prirodan broj između 1 i 1000.

Izlazni podaci

U prvi redak ispiši traženi broj iz teksta zadatka.

Primjer zadatka

Ulaz

6 2
15 16 16 16 15 15

Izlaz

6

Objašnjenje

Opis prvog probnog primjera: U ormaru se nalaze tri čarape veličine 15 i tri čarape veličine 16. Stjepan

smije zadržati sve čarape jer se od njih ne može složiti više od 2 para.

Ulaz

6 2
15 15 15 15 16 16

Izlaz

5

Objašnjenje

Opis drugog probnog primjera: U ormaru se nalaze četiri čarape veličine 15 i dvije čarape veličine 16. Stjepan ne smije zadržati sve čarape jer bi se tada mogla složiti 3 para. Najveći broj čarapa što Stjepan

smije zadržati je pet. (15 15 15 16 16) ili (15 15 15 15 16).

Ulaz

6 2
16 16 16 16 16 16

Izlaz

5

Objašnjenje

Opis trećeg probnog primjera: Stjepan ne smije zadržati sve čarape jer bi se tada mogla složiti 3 para.