Zvrat! Lukáš v kasíne úplnou náhodou stretol Julku. Po dlhej a náročnej diskusií sa rozhodli že to chcú skúsiť znovu. Julka si stále nie je úplne istá svojím rozhodnutím, preto posiela Lukášovi kryptické správy, z ktorých mu nie je jasné, či ho naozaj chce, alebo je iba kamarát. Pomôž Lukášovi dešifrovať tieto správy a zachráň ich vzťah!
Julkina kryptická správa pozostáva z niekoľkých slov, ktoré sa nachádzajú v jej “slovníku”. Slovo je reťazec znakov anglickej abecedy bez medziery. Julka si vyberie niekoľko slov a spojí ich dokopy (odstráni medzery medzi nimi) a takto vznikne jej šifra. Slová sa môžu opakovať. Tvojou úlohou je zistiť, z ktorých miest Julka odstránila medzeru a vypísať pôvodný zoznam slov oddelený medzerou.
**Kasíno je prístupné len pre osoby staršie 18 rokov. Nič v tomto texte nenabáda mladistvých na hazardné hry. Akákoľvek podobnosť s reálnymi hracími automatmi je čisto náhodná a nebola zámerná. Lukáš prehral skoro všetko, zbytok minul na Christian Louboutine Miss Z Black 100mm lodičky a kvety pre Julku. **
V prvom riadku vstupu je číslo $d$ ($1 \leq d \leq 500$) udávajúce počet slov v slovníku. Nasleduje riadok, kde je $d$ slov, oddelených medzerou. Každé slovo má dĺžku najviac $50$ znakov. Tretí riadok je Julkina šifra dĺžky $l$.
| Sada | 1 | 2 | 3 |
|---|---|---|---|
| $1 \leq d \leq$ | $20$ | $100$ | $500$ |
| $1 \leq l \leq$ | $500$ | $50\,000$ | $500\,000$ |
Vypíš jeden riadok a na ňom dešifrovanú Julkinu šifru.
3
benefitmi s kamarat
kamaratsbenefitmi
kamarat s benefitmi
10
moznosti chcem ale alene alex ta nechcem uzavriet ine inemoznos
chcemtaalenechcemuzavrietinemoznosti
chcem ta ale nechcem uzavriet ine moznosti
Tátu úloha sa dala riešiť napríklad takto:
Odzadu sa pozrieme postupne na každé písmeno, pričom pre každé nás zaujíma, či tu mohlo začínať nejaké slovo(vyskúšame všetky v slovníku). Ak tu nejaké slovo mohlo začať, musí končiť buď na konci celej správy, alebo za ním rovno nasleduje ďalšie slovo. Ak to toto slovo spĺňa, zapamätáme si ho.
Poznámka: Môžu nastať prípady, keď toto riešenie nájde aj alternatívne možnosti, ktoré však neskôr zlyhajú. Napríklad pre vstup:
3
t stes test
stest
Môže začínať slovo test na 2. písmene, no nie je to správne riešenie lebo potom nám zostane s, ktoré nevieme nijak dešifrovať. Preto konštruujeme riešenie tak, že začneme na prvom písmene a postupne pridávame slová ktoré začínajú hneď za koncom toho minulého.
Pre každé písmeno teda vyskúšame každé slovo, čo nás dokopy stojí $s$ porovnaní znakov, kde $s$ je súčet dĺžky všetkých slov v slovnúiku. Časová zložitosť tohto riešenia je preto $O(l \cdot s)$
Kód v pythone môže vyzerať takto (autor: Max Molnár)
d = int(input())
slovnik = input().split()
otazka = input()
odpoved = []
for _ in range(len(otazka)+1):
odpoved.append(0)
odpoved[len(otazka)] = ""
for i in range(len(otazka) - 1, -1, -1):
for slovo in slovnik:
if otazka[i:i+len(slovo)] == slovo:
if odpoved[i + len(slovo)]!= 0:
odpoved[i] = slovo
break
if odpoved[0]!=0:
vysledok = []
index = 0
while index < len(otazka):
vysledok.append(odpoved[index])
index += len(odpoved[index])
print(*vysledok)
else:
print(0)
Alternatívne riešenie je, že by sme použili písmenkové stromy (o nich sa viac dočítaš tu). V tomto prípade sa nám zjednoduší skúšanie každého slova, namiesto zložitosti $s$ to dokážeme spraviť v čase $m$, čo je hĺbka písmenkového stromu, respektíve dĺžka najdlhšieho slova.
Časová zložitosť je preto iba $O(l \cdot m)$.
Program v pythone by mohol vyzerať napríklad takto:
class Trie:
def __init__(self):
self.children: dict[str, Trie] = {}
self.is_end_of_word = False
self.parent: Trie | None = None
def insert(self, word: str) -> None:
node = self
for char in word:
if char not in node.children:
node.children[char] = Trie()
node.children[char].parent = node
node = node.children[char]
node.is_end_of_word = True
dictSize = int(input())
dictionary = input().split()
trie = Trie()
for word in dictionary:
trie.insert(word[::-1])
cipher = input()
result = [0] * len(cipher)
result.append("")
for i in range(len(cipher)-1,-1,-1):
currentNode = trie
currentIndex = i
while True:
currentChar = cipher[currentIndex]
if currentChar not in currentNode.children.keys():
break
currentNode = currentNode.children[currentChar]
currentIndex -= 1
if currentNode.is_end_of_word:
if result[i+1] != 0:
result[currentIndex+1] = cipher[currentIndex+1 : i+1]
answerIndex = 0
answer = ""
while answerIndex < len(cipher):
answer += result[answerIndex] + " "
answerIndex += len(result[answerIndex])
print(answer)
Súťaž PRASK zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre stredoškolákov
Tímová matematicko-fyzikálna súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania