D1 - Flochia encyklopédia

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

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3.4, Python 3.11

Počet bodov: 1

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

Viete, čo je floch? Floch je malé zelené zvieratko, ktoré pri rozprávaní strašne bľaboce (je to asi preto, že má veľmi dlhý jazyk, ktorým sa nedá dobre artikulovať).
Bľabotanie flochov je pomerne jednoduché a spočíva v tom, že sa aspoň dvakrát zopakuje začiatok aj koniec vety. Ak chce floch povedať "syseľ je chudák", môže namiesto toho povedať "sysesysesysesyseľ je chudákákákákák", ale aj "sssssssyseľ je chudák" (v tomto prípade sa zopakoval koniec dĺžky 0), nie však "syseľ jeje chudákchudák".

Viete, čo flochy robia najradšej? Skáču a lovia hmyz.
Okrem toho občas napíšu aj nejakú knihu. Napríklad minule to bola Encyklopédia o skákaní a lovení hmyzu, v ktorej si dali obzvlášť záležať na poriadnom bľabotaní. Táto encyklopédia sa veľmi ujala (vďaka zvolenej téme aj poriademu bľabotaniu), a tak sa vydavateľstvo rozhodlo vydať jej vreckové vydanie.

Viete, kde žijú flochy? Vo Švajčiarsku samozrejme.
Aby bolo vreckové vydanie čo najkratšie, rozhodli sa texty skomprimovať. Keďže flochy nevedia veľmi dobre programovať (veď žijú vo Švajčiarsku), potrebujú, aby ste im s tým pomohli.

Úloha

Najrozumnejší spôsob komprimácie je zakódovať vety do tvaru X[začiatok] + [stred] + Y[koniec], kde X,Y sú celé čisla veľkosti aspoň 2 a [začiatok], [stred] a [koniec] sú reťazce znakov (ktoré môžu mať aj nulovú dĺžku).
Napríklad, "sysesysesysesyseľ je chudákákákákák" sa dá skomprimovať napríklad ako 4"syse" + "ľ je chudákák" + 3"ák", alebo aj 2"sysesyse" + "ľ je chud" + 5"ák", nie však 8"sy" + "ľ je chud" + 5"ák" ani 1"sysesysesysesyse" + "ľ je chudák" + 4"ák".
Vašou úlohou je skomprimovať vety tak, aby súčet dĺžok reťazcov [začiatok], [stred] a [konciec] bol čo najmenší. Napríklad najlepšia komprimácia "sysesysesysesyseľ je chudákákákákák" je 4"syse" + "ľ je chud" + 5"ák" s celkovou dĺžkou 4 + 9 + 2 = 15.
Aby sa dala encyklopédia čo najlepšie skomprimovať, vymazali sa všetky medzery a diakritika. Vety sa teda budú skladať iba z malých písmen anglickej abecedy.

Vstup

Viete, podľa akého vzoru sa skloňuje floch? Pokiaľ sa vám to nepodarilo odpozorovať, tak prezradím, že je to ako pri iných zvieratkách mužského rodu - v jednotnom čísle podľa vzoru chlap a v množnom podľa vzrou dub (pretože ch je tvrdá spoluhláska).
Na vstupe je najviac 50 riadkov, na každom je jedna veta - reťazec malých písmen anglickej abecedy.

Výstup

Viete, ako sa povie floch po latinsky? Nie? Ani ja.. ale po maďarsky je to Svájci béka.
Pre každý riadok vstupu vypíšte jeho najlepšiu komprimáciu. Ak je správnych možností viac, vypíšte ľubovoľnú z nich.
Formát výstupu je X začiatok + stred + Y koniec, pričom časti nulovej dĺžky nevypisujte.

D1

Dĺžka každého riadku je najviac 50.

D2

Dĺžka každého riadku je najviac 10⁵.

Príklad

Vstup:

sysesysesysesyseljechudakakakakak
floch
zazazaba
zazababa
flfflffflfff

Výstup:

4 syse + ljechud + 5 ak
floch
3 za + ba
2 za + 2 ba
2 flf + ffl + 3 f

10 Finále 1