Problem F
Akureyri

Árið 2016 er merkilegt ár fyrir Forritunarkeppni Framhaldsskólanna. Í fyrsta skipti í sögu keppninnar verður keppnin haldin á tveimur stöðum! En nú er árið 3016 og keppnin er haldin um allt land, ekki bara í Reykjavík og Akureyri. Keppendur fara ekki lengur á keppnina, heldur kemur keppnin til þeirra. En skipulagsteymi forritunarkeppninnar er í miklum vandræðum með að skipuleggja bolina fyrir keppendur þetta árið. Keppendur eru nú í þúsundum, jafnvel tugþúsundum en það er alltof stutt í keppnina svo að hægt sé að fara yfir þetta í höndunum. Á árinu 3016 er fólk svo vant því að tölvur forriti fyrir fólk, fyrir utan stöku snillinga sem eru að keppa í Forritunarkeppni Framhaldskólanna að skipuleggjendurnir eru búnir að steingleyma hvernig á að forrita og hafa ekki hugmynd hvernig þetta vandamál væri leysanlegt í tölvu.

Sem betur fer var ákveðið að frysta Hjalta árið 2016 og geyma hann í djúpsvefni ef ske kynni að skipuleggjendur yrðu í svo miklum vandræðum að geta ekki leyst úr flækjunni sjálf. Það sem skipuleggjendurnir þurfa hjálp Hjalta við er að fara yfir keppendalistann og skrá niður hversu marga boli þarf að senda á hvern stað á landinu. Hjalti er hins vegar búinn að vera sofandi í 1000 ár og er því svolítið ringlaður. Hjálpaðu Hjalta að redda málunum!

Inntak

Inntakið byrjar á einni línu sem inniheldur staka heiltölu $1\leq N\leq 10\, 000$ sem er fjöldi keppenda. Næst fylgja $N$ pör af línum, samtals $2N$ línur. Í hverju pari af línum inniheldur fyrri línan nafn keppanda en seinni línan staðsetningu hans. Báðir strengirnir samanstanda eingöngu af enskum bókstöfum. Þeir munu innihalda að minnsta kosti einn staf og aldrei fleiri en $100$ stafi.

Úttak

Fyrir hvert bæjarfélag sem birtist sem staðsetning keppanda, prentið út nafn bæjarfélagsins og síðan fjölda keppanda sem staðsettir eru í tilteknu bæjarfélagi. Prenta má þennan lista út í hvaða röð sem er.

Útskýring á sýnidæmum

Í fyrsta sýnidæmi eru tveir keppendur á Akureyri, þeir Bjarki og Jonas en hins vegar eru Hjalti, Gunnar og Tomas í Reykjavik og gefur því þetta úttakið sem sýnt er.

Stigagjöf

Lausnin mun verða prófuð á miserfiðum inntaksgögnum, og er gögnunum skipt í hópa eins og sýnt er í töflunni að neðan. Lausnin mun svo fá stig eftir því hvaða hópar eru leystir.

5
Hjalti
Reykjavik
Gunnar
Reykjavik
Bjarki
Akureyri
Tomas
Reykjavik
Jonas
Akureyri

Akureyri 2
Reykjavik 3

2
Bjarki
Akureyri
Jonas
Akureyri

Akureyri 2

2
Sunna
Selfoss
Saga
Akureyri

Akureyri 1
Selfoss 1