Ianus Timidus Ordinator sa nestal senátorom náhodou. K postaveniu mu okrem pôvodu pomohli všemožné intrigy, ale hlavne perfektné porozumenie mestu a jeho obyvateľom. Väčšinu z nich síce tvoria neušľachtilí a kultúrne zaostalí plebejci, aj tí však vedia byť, pri správnom nasmerovaní, nesmierne užitoční. Napríklad platia dane, s radosťou šíria rôzne starostlivo vymyslené klebety, a občas sa vzbúria proti oponentom, ktorých treba práve zosadiť z mramorových lavíc.
Na oplátku im stačí málo – chlieb a hry. Chlieb preto, že s plnými ústami sa ťažko sťažuje. Hry zase slúžia na ventiláciu frustrácie z vlastného života – nie je predsa nič upokojujúcejšie, ako sledovať profesionálneho gladiátora zvádzať krvavý boj na život a na smrť s divokou šelmou z ďalekej Afriky.
Každá hra sa však postupne ohrá a potrebuje nejakú zmenu. A keďže naučiť levy žrať gladiátorov novými, zaujímavejšími spôsobmi sa nedarí, Ianus sa rozhodol pri organizovaní ďalších hier trochu ozvláštniť pravidlá boja…
Boj nebude prebiehať celý naraz, ako to bývalo doteraz, ale bude sa riadiť losovaním písmen z mešca (výborne, to pridá celej akcií určitý moment prekvapenia, a možno konečne podnieti poriadny rozmach stávkovania!). Pri vytiahnutí nového písmena sa skontroluje, či je možné zo všetkých doteraz potiahnutých písmen poskladať prezývku nejakého gladiáta v aréne. Ak áno, všetci gladiátori, ktorých prezývka sa dá poskladať, idú okamžite bojovať s levmi… a ak niektorý z nich boj náhodou prežije, získa slobodu a posadí sa do hľadiska.
Extrémne dôležité je tu slovo okamžite – to najhoršie, čo sa môže stať, je, že po potiahnutí písmena budú zodpovední úradníci tak dlho premýšlať nad tým, ktorých gladiátorov poslať do boja, až to plebejcov prestane baviť, z arény nahnevane odídu, rozhádžu všade popcorn a možno vyplienia polku mesta. Je teda nutné zabezpečiť, že všetko pôjde ako po masle.
Dostanete zoznam prezývok všetkých gladiátorov v aréne, tvorených malými písmenami abecedy (ako inak, latinskej), a malými rímskymi čislicami. Ďalej budete dostávať poradie, v ktorom sa z mešca ťahajú písmená.
Pre každé potiahnuté písmeno vypíšte počet gladiátorov vyslaných do boja po jeho potiahnutí.
Pozor, na otázky musíte (s výnimkou druhej sady) odpovedať online, teda ďalšiu otázku dostanete vždy až potom ako odpoviete na predošlú!
V prvom riadku vstupu sú čísla $G$ a $L$ oddelené medzerou udávajúce postupne počet gladiátorov a počet písmen ťahaných z mešca. Nasleduje $G$ riadkov s prezývkami gladiátorov, ktorých dĺžka je medzi $2$ a $10^5$. Je garantované, že súčet dĺžok prezývok gladiátorov na vstupe nepresiahne $10^5$. Túto časť vstupu dostanete naraz.
Po nich postupne dostanete $L$ riadkov s písmenami, v poradí v akom sa ťahajú z mešca. Pre každý z nich vypíšte jeden riadok s počtom gladiátorov, ktorí začnú bojovať na základe jeho potiahutia. Okrem druhej sady nedostanete nové písmeno skôr, než vypíšete odpoveď.
Odporúčame zavolať funkciu flush po každom vypísanom riadku,
aby program nečakal, kým sa operačný systém rozhodne vyprázdniť zásobník štandardného výstupu.
V C++ môžete použiť std::cout.flush(),
alebo jednoducho vypisovať nové riadky pomocou std::endl namiesto \n.
V Pythone stačí pridať argument funkcií print(..., flush=True).
Existujú štyri testovacie sady, pričom vo všetkých platí, že $1 \leq G \leq 2\times 10^4$, $1 \leq L \leq 10^5$ a súčet dĺžok prezývok gladiátorov nepresiahne $10^5$. V jednotlivých sadách však platia nasledovné dodatočné obmedzenia:
V prvej sade platí, že $G \leq 100$, $L \leq 100$ a a súčet dĺžok prezývok nepresiahne $1000$.
V druhej sade dostanete všetky otázky naraz – nemusíte teda odpovedať online (ale môžete, testovacie prostredie si s tým poradí).
V tretej sade sa nevyskytujú žiadne mená gladiátorov dlhšie než $50$ znakov.
3 5
xii
xix
xxi
x
i
i
x
i
0
0
1
2
0
Po prvých dvoch ťahaniach nemáme dosť písmen na žiadny súboj. Z davu sa ozýva znudené zívanie a trocha netrpezlivého šomrania.
Po treťom ťahaní už máme jedno x a dve i, takže vieme poskladať xii – a jeden gladiátor je hrdinsky zožratý.
Po štvrtom ťahaní už máme dokomca dve x, takže dokážeme poskladať aj xix a xxi. To je teda akcia!
Pred posledním ťahaním už nezostal žiaden gladiátor, ktorý by bavil publikum. Plebejci sa trúsia von z arény a idú si dať pizzu.
8 10
quis
stultus
hoc
excogitavit
aaaaaa
dii
mei
leo
o
q
u
s
d
i
i
m
l
e
0
0
0
0
0
1
1
0
0
2
Hic sunt leones.
V úlohe pracujme s menami gladiátorov, ktoré dostaneme naraz na začiatku, a sadou písmen, ktoré postupne získavame – tie budeme pre jednoduchosť volať ruka, čo je veľmi originálny a veľmi nesprávny preklad termínu rack z hry Scrabble.
Začnime tým, ako sa dostať k výsledku s čo najmenej rozmýšľaním – uložíme si mená všetkých gladiátorov a pre každú otázku znova a znova určíme, ktoré z mien vieme poskladať z aktuálnej ruky. Pre každého gladiátora si budeme pamätať, či sme ho už do boja poslali, a vždy spočítame tých, ktorí ešte neboli vyslaní, a označíme ich za vyslaných. Tento prístup má časovú zložitosť $\O(GL + S)$ (kde $S$ je celkový počet písmen v menách gladiátorov) a ľahko nám získa dva body za prvú sadu. Poďme si však ešte domyslieť detaily implementácie.
Jedno z najdôležitejších pozorovaní je, že pri písmenách losovaných z mešca, ale aj pri menách gladiátorov, nám v momente porovnávania vôbec nezáleží na poradí písmen, iba na ich počtoch. Mená gladiátorov aj postupne sa zväčšujúcu ruku si teda môžeme reprezentovať ako pole čísel veľkosti abecedy ($26$, keďže malé rímske čísla sú už v písmenách latinskej abecedy obsiahnuté). Meno sa dá poskladať z písmen ruky práve vtedy, ak je každé číslo v jeho poli menšie alebo rovné zodpovedajúcemu číslu v poli ruky. To vieme overiť na jeden priechod cez obe polia.
Keď už vieme riešiť malé sady, skúsme sa pozrieť na tie väčšie, pri ktorých nám úloha sľubuje určité zjednodušenia.
V tejto sade dopredu poznáme všetky písmená pridávané do ruky, pomôže nám to? Hlavný rozdiel oproti iným sadám je, že nemusíme pre každé potiahnuté písmeno zisťovať počty novovytvoriteľných slov – môžeme to spraviť naopak a pre každé slovo si spočítať, kedy sa nám ho podarí prvýkrát vytvoriť. Ku každému potiahnutému písmenu si vytvoríme počítadlo a budeme ho zvyšovať, ak sa nám nové slovo podarí vytvoriť práve vtedy.
Uvedomme si, že každé slovo bude možné prvýkrát vytvoriť po získaní určitého písmena, a pokiaľ sa toto písmeno nachádza v slove viackrát, tak to bude práve potom, čo získame posledný výskyt daného písmena. To nám dáva iba $26$ možností, kedy dané slovo pôjde vytvoriť – a limitujúca je tá, ktorá sa stane najneskôr.
Pre každé písmeno si teda uložíme časy, v ktorých potiahneme jeho výskyty, do obyčajného poľa (a časy už budú rovno správne zoradené). Potom pôjdeme po slovách a pre každé písmeno abecedy si zistíme, či je počet jeho výskytov v slove menší alebo rovný dĺžke poľa pre dané písmeno – ak nie, nikdy nebudeme mať dosť písmen a slovo nezložíme. Ak áno, na indexe zodpovedajúcom počtu výskytov písmena v slove nájdeme limitujúci čas pre dané písmeno (čas, v ktorom konkrétny výskyt daného písmena získame). Zo všetkých limitujúcich časov vezmeme ten najväčší, a počítadlo v danom čase zväčšíme o $1$.
Časová zložitosť je v tomto prípade $\O(G + L + S)$ – stačí si uložiť všetky mená, všetky potiahnuté písmená, a pre každé meno prejsť raz jeho pole veľkosti abecedy.
V tejto sade sú všetky slová krátke, konkrétne dlhé najviac $50$ znakov. Kľúčové pozorovanie je, že hoci existuje $26^{50}$ rôznych slov, nás zaujímajú pre každé slovo iba počty jeho jednotlivých písmen a každé písmeno nás môže svojim počtom limitovať iba raz. Existuje teda $26 \times 50$ rôznych počtov limitujúcich písmen (napríklad $1$-krát a, $2$-krát a…) – môžeme si pre každý z nich vyrobiť pole a do neho uložiť všetky slová, ktoré sú ním limitované.
Slovo sa môže vyskytnúť až v $26$ poliach, musíme si teda dať pozor, aby sme ho nezapočítali viackrát. Budeme si preto do polí ukladať iba jeho index, a pre každé slovo si budeme pamätať, či už sme ho použili.
Spracovávanie dotazov je potom jednoduché – pre novozískané písmeno sa pozrieme do poľa podľa aktuálneho počtu výskytov daného písmena v ruke, pre všetky slová v ňom skontrolujeme, či ich vieme vytvoriť, a či sme ich už náhodou predtým neoznačili za použité. Nové slová globálne označíme za použité.
Všimnime si, že každé pole prejdeme najviac raz – iba vtedy, keď získame zodpovedajúce písmeno v konkrétnom počte. Preto celkovo prebehne najviac $26 \times G$ porovnaní slov s rukou, celková časová zložitosť je teda opäť $\O(G + L + S)$.
Aby sme vyriešili všetky sady naraz, použijeme dátovú štruktúru trie – písmenkový strom, do ktorého postupne vložíme všetky slová. V každom vrchole si označíme, či v ňom končí slovo, a keď sa nám nejaké vrcholy podarí z písmen ruky prvýkrát poskladať, bude odpoveď pre dané ťahanie práve počet týchto vrcholov.
Počas algoritmu si budeme udržiavať fronty “otvorených” vrcholov – takých vrcholov, ktorých rodič v trii sa dá poskladať z písmen v ruke, ale vrchol samotný nie. Je zrejmé, že každý otvorený vrchol je limitovaný práve jedným písmenom – preto bude počet front 26. Na začiatku sú vo frontách všetci potomkovia koreňa trie – prázdneho reťazca. Pokiaľ získame nové písmeno, pozrieme sa do jeho fronty a vyberieme z nej všetky vrcholy, ktoré na dané písmeno čakali – už sa dajú poskladať.
Pre každý vybraný vrchol potom do fronty vložíme jeho deti – musíme si ale dať pozor na to, že niektoré deti a ďalší potomkovia už nečakajú na žiadne písmeno. Napríklad pre slovo abc môžeme písmená dostať do ruky v poradí b, a, c – po získaní písmena a vieme vytvoriť aj jeho dieťa s písmenom b a teda do fronty vložíme až vrchol s písmenom c. Preto pre každého potomka určíme, ktorým písmenom je limitovaný; ak žiadnym nie je, pokračujeme s jeho potomkami (napríklad tým, že ich pridávame do fronty)… musíme ešte vyriešiť potomkov, ktorí skončia v aktuálnej fronte (čakajúc na práve získané písmeno, ale vo väčšom počte výskytov) – napríklad tak, že si ich odložíme nabok a na konci prehľadávania vrátime do fronty.
Tento prístup nám zabezpečí, že každý vrchol trie otvoríme najviac raz, najviac raz ho označíme za poskladateľný, a nikdy viac ho už nekontrolujeme. Časová zložitosť teda bude $\O(G + L + S)$ a pamäťová $\O(S)$.
Z praktického hľadiska môžeme pri vytváraní stromu ešte využiť fakt, že na poradí písmen v slovách nezáleží. Pokiaľ písmená v každom slove utriedime a pre každý vrchol si budeme pamätať koľko slov v ňom končí, súčet hodnôt dosiahnutých vrcholov bude výsledok pre každé ťahanie. Vďaka tomu bude stačiť vyrobiť menej vrcholov stromu, hoci asymptoticky sa algoritmus nezlepší.
Alebo ako ohnúť tretiu sadu aj tam, kde neplatia zjednodušenia tretej sady.
Ak chceme riešenie, ktoré môže byť teoreticky pomalé, ale prakticky rýchle, a jednoduché na implementáciu, môžeme upraviť riešenie pre tretiu sadu, ktoré použijeme pre všetky krátke slová. Samozrejme sa nám v ostatných sadách môžu vyskytnúť aj dlhšie slová, tie si ale jednoducho odložíme a spracujeme naívne, ako v triviálnom riešení pre prvú sadu – teda po každom získanom písmenku všetky z nich prejdeme a tie, ktoré ešte neboli použité a dajú sa vyrobiť, označíme ako použité.
Teoreticky má toto riešenie kvadratickú časovú zložitosť. Vieme si ale nastaviť takú hranicu dĺžky krátkych slov, pre ktorú sa nám jednotlivé polia z tretej sady stále s prehľadom zmestia do pamäte – napríklad $10^4$ ($260000$ prázdnych polí zaberá iba niekoľko MB, čo je takmer nič, pokiaľ máme štandardne k dispozícii 1 GB pamäte), v takom prípade už z limitov zadania na počet slov a ich celkovú dĺžku nemôže existovať viac než $10$ slov, ktoré budeme považovať za dlhé – tie môžeme bez problémov overiť po každom potiahnutom písmenku. V praxi stačilo použiť limit dĺžky $50$ z tretej sady.
Ak by sme chceli dosiahnuť aj teoreticky dobrú časovú zložitosť, môžeme ako maximálnu dĺžku slova použiť $L$ – pokiaľ bude mať nejaké slovo viac písmen určitého druhu, určite sa nebude dať nikdy poskladať. Preto nám nezostanú žiadne dlhé slová, ktoré by sme museli spracovávať po každom ťahaní.
Táto myšlienka vedie na ďalšie jednoduché riešenie. Pre každé slovo si spočítame všetky jeho písmená. Pre každé písmeno si vyrobíme pole dĺžky $L$, kde si pre každý počet výskytov daného písmena uložíme index slova s daným počtom výskytov. Okrem toho si pre slovo uložíme počet rôznych písmen, ktoré sa v ňom vyskytujú nenulový počet krát. Keď potom potiahnem písmeno, pozrieme sa na všetky slová, ktoré máme uložené s jeho aktuálnym počtom výskytov, a ich počítadlá rôznych písmen znížime o $1$. Ak nejaké z nich klesne na nulu, podarilo sa nám poskladať nové slovo.
Keďže na každé slovo sa pozrieme najviac $26$-krát, bude aj toto riešenie mať časovú zložitosť $\O(G + L + S)$. Do pamäte sa nám zmestí na základe podobnej úvahy ako predošlé riešenie.
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete