Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabovi na [email protected]
Adam sa minulú nedeľu, ako vzorný vnuk, rozhodol zavolať svojej babke. Jej telefónne číslo si pamätá odmala, začal ho preto vyťukávať do mobilu. V polovici písania však Adamova obrazovka vyzerala zhruba takto a kontakt na babku bol automaticky doplnený.

Adam sa zháčil. Takúto funkcionalitu pokladal za samozrejmú, nikdy sa však nezamyslel, ako to vlastne ten mobil robí. Podľa čoho si vie tipnúť zadávané číslo a dokonca povedať koľko ďalších možností ešte existuje? Zrazu zabudol na to čo robil a začal sa vŕtať v pamäti telefónnu. Pomôžte Adamovi odpovedať na jeho otázky, nech stihne zavolať babke.
Úloha
- (1 body) Adam si do mobilu stiahol program, ktorý mu umožňuje prezerať si vnútornú pamäť telefónnu. Hneď ho aj spustil s tým, že mu má zobraziť pamäť patriacu kontaktom. Program preňho vygeneroval nasledovný obrázok.

Adam však vôbec nerozumie tomu, čo má táto reprezentácia znamenať. A jediný kontakt, ktorý si pamätá je na jeho babku, ktorá má číslo 8623
(nečudujte sa, štvormiestne čísla sú tam kde žije Adam úplne bežné).
Z uvedeného obrázku vydedukujte, aké všetky kontakty má Adam uložené v telefónne. Pre každý kontakt určite aj telefónne číslo, ktoré mu prislúcha.
- (2 body) Ako by vyzeral obrázok vygenerovaný stiahnutým programom, ak by mal Adam uložené nasledovné kontakty:
mama: 091576 ujo: 091497 brat: 091256 janka: 092730
sestra: 092576 stryko: 091483 lucka: 092578 sysel: 093037
babka: 091547 peter: 092530 jonas: 092098 radka: 091418
(4 body) Adama by zaujímalo, ako vie jeho mobil pomocou uvedenej reprezentácie dopĺňať kontakt, ku ktorému by dané číslo mohlo patriť. Vašou úlohou je vymyslieť postup, ktorý po zadaní niekoľkých prvých cifier čísla nájde ľubovoľný kontakt, ktorého číslo začína na zadané cifry. Poprípade oznámi, že žiadny taký kontakt sa v mobile nenachádza.
Napríklad, ak by sme sa pozreli na kontakty z podúlohy b), tak po napísaní
0914
by Adamov mobil mohol navrhnúť kontaktradka
ale takisto kontaktyujo
alebostryko
. A v prípade, že by Adam napísal iba0
, mohol by mu mobil ponúknuť ľubovoľný z jeho kontaktov. Ak by sa však pomýlil a napísal by08
ako začiatok čísla, mobil by mu povedal, že žiaden vhodý kontakt neexistuje.Vaše riešenie by malo fungovať pre každú možnú množinu kontaktov. Jednak sa teda môže meniť počet kontaktov a takisto dĺžka jedného čísla. Môžete však predpokladať, že všetky čísla majú rovnakú dĺžku a že tieto kontakty sú v pamäti reprezentované rovnako ako v podúlohách a) a b).
Taktiež sa snažte, aby bolo vaše riešenie čo najefektívnejšie, teda potrebovalo spraviť čo najmenej úkonov. Napríklad ak by sme mali \(10\,000\) desaťmiestnych telefónnych čísel zapísaných vo vyššie uvedenej štruktúre, optimálne riešenie by sa stále dalo simulovať aj ručne.
(5 body) Keď Adam do pamäte zapísal dlhšie čísla, hral sa aj s 1000 cifernými číslami, zdalo sa mu, že mu mobil začal sekať. Niekde v nastaveniach však našiel tlačidlo “Zoptimalizuj kontakty”, ktoré po stlačení citeľne urýchlilo dopĺňanie kontaktov. Keď sa opäť pozrel do pamäte telefónnu, s prekvapením zistil, že jej reprezentácia sa zmenila.

Upravte váš postup z podúlohy c) tak, aby využíval nové údaje z pamäte. Prečo je toto riešenie rýchlejšie ako to predošlé? Okrem toho vymyslite postup, ktorým boli hodnoty dopln
vypočítané. Máte teda popísať postup, ktorý sa vykoná keď je stlačené tlačidlo “Zoptimalizuj kontakty”, a ktorý doplní do pamäte nové hodnoty. Tento postup by mal fungovať na ľubovoľnej množine kontaktov.
- (3 body) S počítaním možností je však stále problém. Síce to Adamov mobil robí správne, trvá mu to príliš dlho. A žiadne tlačidlo “Zoptimalizuj počet” neexistuje. Rozhodol sa preto, že si ho do mobilu doprogramuje, nevie však, ako má toto tlačidlo pracovať. Vymyslite a podrobne popíšte čo sa má stať po stlačení tlačidla “Zoptimalizuj počet”. Následne popíšte, ako bude telefón pre zadaný začiatok čísla zisťovať počet čísel s rovnakým začiatkom.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.