ŠIOM — Svečiai iš Japonijos

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1999_3e2_japonai_vyr.in

Rezultatų failas: lmio_1999_3e2_japonai_vyr.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Svečiai iš Japonijos

Mokykloje apsilankė moksleivių iš Japonijos delegacija. Atvykus svečiams buvo surengta vakaronė per kurią jie susipažino su vietiniais moksleiviais. Vakare vietiniai moksleiviai turėjo pasidalinti svečius po namus, kur jie gyventų visą viešnagės laiką. Vienam moksleiviui leidžiama apnakvydinti tik vieną svečią. Mokytojas surinko vietos moksleivių pageidavimus. Kiekvienas moksleivis pateikė sąrašą svečių, su kuriais jis susipažino ir vieną iš kurių jis sutiktų priimti.

Užduotis

Parašykite algoritmą, kuris padėtų mokytojui paskirstyti svečius taip, kad patenkintų moksleivių (vietinių ir svečių) skaičius būtų didžiausias. Savaime suprantma, kad visi japonai turi būti apgyvendinti. Pastaba. Moksleivio pageidavimas laikomas abipusiu sąryšiu: t. y. jei Jonas nori apgyvendinti Chau Youd, tai reiškia, kad Chau Youd sutinka gyventi pas Joną. Ir analogiškai, jei Petras nenori priimti Chau Youd ir jo neįtraukė į savo sąrašą, tai reiškia, kad Chau Youd taip pat nenori gyventi pas Petrą.

Pradiniai duomenys

Pirmoje eilutėje pateiktas vietinių moksleivių skaičius $n$ bei svečių skaičius $m$ . Laikoma, kad vietiniai moksleiviai sunumeruoti nuo 1 iki $n$ , japonai – nuo 1 iki $m$ . Likusiose $n$ eilučių įrašyti vietinių moksleivių pageidavimai. Vieno moksleivio pageidavimams skiriama viena eilutė. Taigi antroje eilutėje įrašyti pirmojo moksleivio pageidavimai, trečioje – antrojo ir t.t. Pirmasis skaičius eilutėje reiškia sąrašo ilgį $ilg$ , likusieji $ilg$ skaičių – japonų, kuriuos norėtų apgyvendinti moksleivis, numerius.

Rezultatai

Failą turi sudaryti $m$ eilučių. i-toje eilutėje turi būti įrašytas vietinio moksleivio, kuris apgyvendins i-tąjį japonų moksleivį, numeris.

Pavyzdžiai

Pradiniai duomenys	Rezultatai	Paaiškinimas
5 4 1 1 2 1 3 3 2 3 4 1 3 1 3	2 3 5 1	Pirmasis vietinis moksleivis sutinka priimti tik pirmą japoniuką, antrasis – pirmą ir trečią ir t.t. Paskirsčius moksleivius, pirmąjį japoniuką priims antrasis moksleivis, antrąjį trečiasis ir t.t. Taip paskirsčius iš devynių moksleivių bus patenkinti šeši: trys vietiniai ir trys svečiai.

Pradiniai duomenys

Rezultatai

Paaiškinimas

2 3 5 1

Pirmasis vietinis moksleivis sutinka priimti tik pirmą japoniuką, antrasis – pirmą ir trečią ir t.t.
Paskirsčius moksleivius, pirmąjį japoniuką priims antrasis moksleivis, antrąjį trečiasis ir t.t.
Taip paskirsčius iš devynių moksleivių bus patenkinti šeši: trys vietiniai ir trys svečiai.

Ribojimai

$1\\leqn,m\\leq50;n\\leqm$

Šeštadieninė informatikos olimpiadininkų mokykla

Svečiai iš Japonijos

Užduotis

Pradiniai duomenys

Rezultatai

Pavyzdžiai

Ribojimai