Državno natjecanje 2021. / Osnovna škola (6. razred) - 1. zadatak

Na informatičkom kampu na kojem sudjeluje M učenika održava se N radionica. Radionice su označene brojevima od 1 do N, a učenici brojevima od 1 do M. Svaki učenik sudjelovat će na točno jednoj radionici.

Kako se u učionici ne bi stvarala prevelika gužva, svaka radionica ima određen maksimalni broj polaznika koji je mogu pohađati. Organizatori moraju smjestiti učenike u radionice ovisno o njihovim preferencijama i bodovima koje su ove godine skupili na županijskom natjecanju iz informatike.

Za svakog učenika zadan je niz od N različitih prirodnih brojeva manjih ili jednakih N koji redom, počevši od oznake radionice na kojoj bi najrađe sudjelovao označavaju njegove preferencije. Organizatori će učenike smještati u radionice poretkom koji je određen njihovim brojem bodova na županijskom natjecanju.

Učenici s više bodova bit će smješteni prije, a ako neka dva učenika imaju isti broj bodova, prioritet dobiva onaj s manjom oznakom. Svaki učenik se smješta u njemu najdražu radionicu čiji kapacitet dosad nije popunjen.

Tvoj zadatak je za svakog učenika odrediti koju će radionicu pohađati. Garantiramo da će rješenje postojati.

Ulazni podaci

U prvom retku nalaze se prirodni brojevi M i N (1 ≤ M, N ≤ 100), brojevi iz teksta zadatka.

U drugom retku je M nenegativnih cijelih brojeva pi (0 ≤ pi ≤ 200), i-ti od njih predstavlja broj bodova i-tog učenika na županijskom natjecanju.

U trećem retku je N prirodnih brojeva ci (1 ≤ ci ≤ 100), i-ti od njih predstavlja maksimalni broj polaznika koji mogu pohađati i-tu radionicu.

Slijedi M redaka po N prirodnih brojeva brojeva gdje i-ti od tih redaka predstavlja preferencije i-tog učenika kao što je opisano u tekstu zadatka.

Izlazni podaci

Ispiši M prirodnih brojeva tako da i-ti od njih bude oznaka radionice koju će pohađati i-ti učenik.

Primjeri test podataka

Ulaz

3 4
200 14 47
1 1 1 1
3 4 2 1
3 4 1 2
1 2 4 3

Izlaz

3 4 1

Ulaz

4 2
40 40 20 30
3 1
1 2
1 2
1 2
1 2

Izlaz

1 1 2 1

Ulaz

3 2
20 50 20
1 3
1 2
2 1
1 2

Izlaz

1 2 2

Objašnjenje

Na kampu je troje učenika i njih treba rasporediti u dvije radionice. Učenici su redom osvojili 20, 50 i 20 bodova na županijskom natjecanju.

Prvu radionicu može pohađati najviše jedan, a drugu najviše tri učenika. Prvi i treći učenik preferiraju prvu, dok je drugom učeniku draža druga radionica.

Najviše bodova na županijskom natjecanju osvojio je drugi učenik pa prvo njega smještamo u njemu najdražu, drugu radionicu.

Prvi i treći učenik su osvojili isti broj bodova pa sad smještamo prvog jer ima manju oznaku.

On preferira prvu radionicu pa ga smještamo u nju. Na kraju moramo odrediti radionicu trećeg učenika.

Njemu je najdraža prva radionica, no u njoj je već postignut maksimalni broj polaznika pa ga smještamo u drugu.