Školsko natjecanje iz informatike 2017. / Srednja škola / Druga podskupina (3. i 4. razred) - 1. zadatak

Preferencijalno glasovanje je sustav u kojem građani, osim mogućnosti glasovanja za određenu izbornu listu, mogu i zaokružiti određenog kandidata na toj listi. Ovaj sustav u Hrvatskoj koristio za parlamentarne izbore 2016. godine te za izbore za Europski parlament 2013. godine. Za potrebe ovog zadatka, razmatramo pojednostavljenu verziju jednog aspekta sustava.

Izborna lista se sastoji od n kandidata označenih redom brojevima od 1 do n, a svaki od kandidata je na izborima dobio određen broj glasova. Ukupan broj glasova liste je jednak sumi glasova svih pojedinih kandidata. Kažemo da je kandidat preferiran ako je dobio najmanje 10% od ukupnog broja glasova liste. Pretpostavimo da točno m kandidata s liste ulaze u parlament, oni se jedan po jedan određuju dok se ne popuni m mjesta prema sljedećim pravilima:

• U parlament ulaze najprije preferirani kandidati i to redoslijedom od onih s više glasova prema onima s manje. Ukoliko dva ili više preferiranih kandidata ima jednak broj glasova, u parlament najprije ulazi onaj od njih koji je označen najmanjim brojem.

• Kada nema više preferiranih kandidata, u parlament ulaze ostali kandidati s liste redoslijedom od onih označenih manjim brojem prema onima označenih većim brojem.

Zadana je izborna lista zajedno s brojem glasova za pojedine kandidate te ukupnim brojem parlamentarnih mjesta koje je lista osvojila. Odredite koji kandidati ulaze u parlament.

Ulazni podaci

U prvom redu nalaze se prirodni brojevi n i m (n ≤ 20, m ≤ n) — broj kandidata na listi te broj parlamentarnih mjesta koje je lista osvojila. U i-tom od sljedećih n redova nalazi se cijeli broj gi (0 ≤ gi ≤ 106 ) — broj glasova koje je osvojio kandidat i.

Izlazni podaci

Ispišite niz od točno n znakova bez razmaka — i-ti znak treba biti “1” ukoliko je kandidat i izabran u parlament odnosno “0” ako nije.

Primjeri test podataka

ulaz

4 2
20
30
30
40

izlaz

0101

ulaz

6 4
2
3
0
10
5
80

izlaz

110101

ulaz

5 3
30
30
30
10
40

izlaz

11001

Pojašnjenje: U prvom primjeru su svi kandidati preferirani pa su izabrana dva kandidata s većim brojem glasova. U drugom primjeru su kandidati 4 i 6 preferirani te su izabrani, još su izabrani kandidati 1 i 2 jer imaju najmanje oznake unatoč manjem broju glasova od kandidata 5.