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

U tijeku je glasanje za ravnatelja gimnazije, a nastavnici pristižu u učionicu glasati za Nikolu.

Učionica je epidemiološki podijeljena u R redova, a svaki je red određen rasponom početnih slova prezimena osoba kojima je namijenjen.

Primjerice, red A-D namijenjen je osobama čije prezime počinje slovom A, slovom B, slovom C ili slovom D (koristimo englesku abecedu).

Prvi red počinje slovom A, a svaki sljedeći red nastavlja s abecedom tamo gdje je prošli red stao, bez preklapanja. Posljednji red završava slovom Z.

Osobe sa samo jednim prezimenom po dolasku će stati u odgovarajući red prema prvom slovu svog prezimena.

Osobe koje imaju više od jednog prezimena, odvojenih crticama, odabrat će odgovarajući red za bilo koje od svojih prezimena, ali tako da od mogućih redova odaberu onaj u kojem je u tom trenutku najmanje ljudi.

Ako postoji više takvih redova, odabrat će onaj koji je prije po abecedi.

Učionica je na početku bila prazna, a na glasanje je došlo N nastavnika koji su stali u redove redom kojim su dolazili.

Ispiši u koji je red stao zadnji nastavnik, kao i sve nastavnike koji se nalaze u redu s najviše ljudi.

Ako postoji više takvih redova, razmatra se onaj koji je prvi po abecedi.

Ulazni podaci

U prvom je retku prirodan broj R (1 ≤ R ≤ 26), broj redova u učionici.

U sljedećih R redaka su opisi raspona redova, kao riječi od tri znaka oblika „x-y“, gdje je x prvo, a y posljednje slovo raspona za taj red. x i y velika su slova engleske abecede, a mogu biti i jednaka. Redovi su zadani abecedno.

U sljedećem je retku broj N (1 ≤ N ≤ 10), broj nastavnika.

U sljedećih N redaka su imena nastavnika redom kojim su dolazili.

Svaki nastavnik zadan je imenom i prezimenom/prezimenima. Prvo slovo imena te prva slova prezimena velika su slova engleske abecede.

Ostala su slova mala slova engleske abecede, s iznimkom crtica kod osoba s više prezimena.

Nijedna dva nastavnika nemaju isto ime niti prezime. Duljina imena, kao i duljina prezimena, neće premašiti 20 znakova.

Izlazni podaci

U prvi redak ispiši raspon reda u koji je stao zadnji nastavnik.

U preostale retke ispiši sve nastavnike u redu s najviše ljudi, jednog po retku.

Ako postoji više takvih redova, razmatra se prvi po abecedi. Nastavnike ispiši abecedno po imenima.

Primjer zadatka

Ulaz

3
A-F
G-G
H-Z
3
Rene Bitorajac
Mirko Filipovic
Petar Graso

Izlaz

G-G
Mirko Filipovic
Rene Bitorajac

Ulaz

3
A-D
E-P
Q-Z
3
Paul Mccartney
Jon Snow
Catherine Zeta-Jones

Izlaz

E-P
Catherine Zeta-Jones
Paul Mccartney

Objašnjenje

Opis drugog probnog primjera: Paul će stati u red E-P, jer slovo M pripada tom redu. Jon će potom stati u red Q-Z. Catherine može stati u redove Q-Z i E-P, jer slovo Z pripada redu Q-Z, a slovo J redu EP. Od ta dva reda odabire onaj s manje ljudi. Budući da je u oba reda po jedna osoba, odabire red koji je prije po abecedi, a to je red E-P. Najviše osoba na kraju je u redu E-P, a to su Catherine i Paul, poredani abecedno po imenu, jer ime Catherine po abecedi dolazi prije imena Paul.

Ulaz

4
A-B
C-D
E-F
G-Z
5
A Ab
C Cd
E Ef
G Gh
I C-E-O

Izlaz

C-D
C Cd
I C-E-O