Prihlásenie Registrácia  

E - Mobil

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Písanie textových správ na klávesnici bežného mobilu (pozri obrázok) je niekedy zdĺhavé. Písmená sa síce dajú ľahko nájsť (sú usporiadané podľa abecedy), ale ich rozloženie nie je optimalizované na rýchle písanie správ. Napríklad na napísanie často sa vyskytujúceho písmena E musíme stlačiť klávesu 3 dvakrát.

Do rúk sa nám dostal nový telefón, ktorý má unikátnu funkciu: dovoľuje nám preprogramovať rozloženie písmen. Hneď sme sa rozhodli túto možnosť vyskúšať. Ale aké rozloženie kláves máme použiť? Dobrý nápad sa zdá byť využiť históriu poslaných textových správ a skúsiť novú klávesnicu optimalizovať pre ne.

Radi by sme vás preto poprosili, aby ste nám napísali program, ktorý by také rozloženie našiel.

Úloha

Daných je niekoľko krátkych textových správ (SMSiek). Úlohou je nájsť také rozloženie písmen na klávesnici mobilného telefónu, ktoré minimalizuje počet stlačených tlačidiel potrebných pre napísanie všetkých písmen daných správ (t.j. ignorujeme znaky, ktoré nie sú písmená). Potrebné je aj nájsť tento minimálny počet a porovnať ho s počtom stlačených tlačidiel pri klasickom rozložení (pozri obrázok). Písmená je možné ukladať len na tlačidlá s číslami 2, ..., 9 a každé písmeno musí byť práve na jednom tlačidle.

Vstup

Prvý riadok vstupu obsahuje jedno celé číslo M (1≤M≤100), počet textových správ. Ďalej nasleduje M riadkov. Každý z nich obsahuje jednu textovú správu. Každá správa sa skladá z aspoň jedného a nanajvýš 180 znakov, pričom povolené znaky sú písmená veľkej anglickej abecedy A..Z, číslice, medzery, čiarky, bodky, otázniky a výkričníky. Môžete predpokladať, že žiadna správa nezačína ani nekončí medzerou.

Výstup

Výstup by mal na prvom riadku obsahovať dve medzerou oddelené čísla: koľko stlačení tlačidiel potrebujeme na napísanie všetkých písmen v daných textových správach na
  1. klasickom (abecednom) rozložení kláves,
  2. optimálnom rozložení kláves.
Ďalej by mal výstup obsahovať jedno optimálne rozloženie kláves. Pre každé tlačidlo 1..9 by mal výstup obsahovať číslo tlačidla nasledované zoznamom písmen na danom tlačidle. Číslo by malo byť oddelené medzerou, medzi písmenami na jednom tlačidle by nemali byť medzery. Výstup môže obsahovať nadbytočné medzery. Tlačidlo 1 by nikdy nemalo obsahovať žiadne písmená.

Príklad

Vstup

2
ZACHVILU PRIDEM, DUFAM, ZE TO STIHNEM NACAS. CAU.
CAU! SORRY, ALE NESTIHAM. MOZEME TO PRELOZIT O 20 MINUT?

Výstup

175 111
1      2 UNF  3 OHG
4 MLYW 5 TZB  6 IRV
7 CSJ  8 ADKQ 9 EPX