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. (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.

1. (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`

1. (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úť kontakt radka ale takisto kontakty ujo alebo stryko. A v prípade, že by Adam napísal iba 0, mohol by mu mobil ponúknuť ľubovoľný z jeho kontaktov. Ak by sa však pomýlil a napísal by 08 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.

2. (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.

1. (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.