Úloha č. 1

Michal nahlas povedal rad čísel: 13, 14, 22, 23, 32. Peter a Janka vedia, ake čísla si Michal myslí. Michal si v hlave vybral jedno z čísel. Petrovi povedal prvú číslicu z čísla, na ktoré myslí. Janke povedal druhú číslicu z čísla, na ktoré myslí. Peter povedal: „Viem, že Janka nemôže určiť, na ktoré číslo Michal myslí.” Janka na to odpovedala: „Je pravda, že som to nevedela, ale teraz to už viem.”

Otázka:
Na aké číslo Michal myslel?

Úloha č. 2

Dvaja kolegovia, Pavol a Isabella, si urobili prestávku na kávu.
Pavol hovorí: „Stavím sa s tebou o ďalšiu kávu, že ako fanúšik jazdectva si si zvolila meno jedného zo svojich koní ako heslo pre tvoj počítač.“ „Je to celkom dobre možné, ale o svojom hesle sa prirodzene nebudem s každým baviť,“ odpovedá Isabel. „Ak sa však trocha pousiluješ, dozvieš sa ho.“ Urobí si poznámku na troch kúskoch papiera a uloží tieto papiere do radu písmom nadol (t.j. zakryté) pred Paula.
Potom povie: „Na dvoch papieroch je správne heslo, na jednom nesprávne. Máš za úlohu ukázať na jeden z týchto troch papierov a spýtať sa jednoduchú otázku áno-nie. Z odpovede môžeš jasne vydedukovať, na ktorom z týchto troch je napísané moje správne heslo. Je tu však jedno obmedzenie. Ak ukážeš na správne heslo, odpoviem pravdivo, ak naopak ukážeš na nesprávne, odpoviem náhodne: zaklamem alebo poviem pravdu. Tak poď!“

Otázka 1:
Na ktorú kartu musí Paul ukázať a akú (jedinú) otázku musí položiť, aby s istotou zistil heslo Isabelly z troch poznámkových papierov?

Otázka 2:
Správajú sa protagonisti správne z hľadiska bezpečnosti a ochrany súkromia?

Otázka 3:
Povedzte nám svoju najoriginálnejšiu mnemotechnickú pomôcku na zapamätanie hesiel.

Úloha č. 3

Raz v noci k malej Aničke priletela víla a povedala jej túto rozprávku na dobrú noc:

Sdqa sdq zmvh sdvqu hlua n iwgd ilvq zqnwsmkwo hvqtt sdna la sdq xvqgqhmac hnj. Nah udqa gmahqvqoon nxxqnvqh ns sdq uqhhmac ma sdmt hvqtt, qrqvj laq unt ntslamtdqh ns dqv zqnwsj. Sdq fmac't tla dnh unmsqh wasmo tdq gniq, nah matsnasoj sllf dqv zj sdq dnah nah hnagqh umsd al laq zws dqv.  Udqa lsdqvt gniq nah marmsqh dqv, dq tnmh, sdmt mt ij xnvsaqv.  Udqa qrqamac gniq tdq umtdqh sl oqnrq, nah sdq fmac't tla klooluqh dqv nah unasqh sl tqq masl udmgd dlwtq tdq uqas.  Zws tdq txvnac nunj kvli dmi, nah masl sdq cnvhqa zqdmah sdq dlwtq.  Sdqvqma tsllh n zqnwsmkwo snoo svqq la udmgd dwac sdq ilts incamkmgqas xqnvt.  Tdq gonizqvqh tl amizoj zqsuqqa sdq zvnagdqt omfq n tewmvvqo sdns sdq fmac't tla hmh als falu udqvq tdq unt claq.  Dq unmsqh wasmo dqv knsdqv gniq, nah tnmh sl dmi, sdq wafalua inmhqa dnt qtgnxqh kvli iq, nah M zqomqrq tdq dnt gomizqh wx sdq xqnv-svqq.  Sdq knsdqv sdlwcds, gna ms zq gmahqvqoon.  Nah dnh na npq zvlwcds nah gws sdq svqq hlua, zws al laq unt la ms.  Nah udqa sdqj cls masl sdq fmsgdqa, gmahqvqoon onj sdqvq nilac sdq ntdqt, nt wtwno, klv tdq dnh ywixqh hlua la sdq lsdqv tmhq lk sdq svqq, dnh snfqa sdq zqnwsmkwo hvqtt sl sdq zmvh la sdq omssoq dnbqo-svqq, nah xws la dqv cvqj clua.

Otázka:
Víly majú vo svojej čarovnej krajine svoju vlastnú abecedu, vieš ju rozlúštiť a zistiť názov rozprávky, ktorú víla povedala malej Aničke? Víla bola angličanka, preto aj text aj rozprávka sú v angličtine.

Úloha č. 4

Kolega Miloš nám vyrozprával zaujímavý príbeh. Včera som mal zvláštny sen. V tomto sne som získal zvláštnu schopnosť, že sa viem pozrieť do budúcnosti. Vedel som však aj to, že táto moja nová schopnosť bude trvať len jeden deň, hneď zajtra zanikne. Rozhodol som sa preto hneď využiť tento dar a navýšiť svoje úspory nákupom a následne výhodným predajom akcií spoločnosti Apple. Vybral som sa preto do svojej banky. Vo svojej banke možem zadať len jeden príkaz na nákup a jeden príkaz na predaj akcií v daný deň, to by mi ale malo stačiť.

Využil som svoju novú schopnosť a stiahol som si súbor z “budúcnosti” s cenovými pohybmi akcií spoločnosti Apple. Súbor obsahoval cenu akcií za každú desatinu sekundy zo zajtrajšieho dňa. Za každú desatinu sekundy jeden číselny údaj, za 24 hodín môj súbor z budúcnosti obsahoval 860 tisíc údajov.

Hmm, zamyslel som sa. Ako teraz zistím, kedy je pre mňa najvýhodnejší čas na nákup, a kedy mám následne dať akcie odpredať? Napadla mi našťastie hneď jednoduchá myšlienka. Stačí mi predsa urobiť rozdiel všetkých možných dvojíc, a ten rozdiel, ktorý bude najväčší, mi predsa dá rozdiel medzi najnižšou a najvyššou cenou. Pre tieto časy nastavím príkaz na nákup a na predaj akcií.

Na manuálne počítanie súbor obsahoval veľa údajov, keďže som ale kodér, rýchlo som priamo v banke napísal program, ktorý urobí rozdiel všetkých možných dvojíc zo súboru, ktorý som stiahol z budúcnosti. Program som hneď spustil a čakal.

Jednu vec som ale podcenil. Všetky možné dvojice znamenalo vyrátať asi 400 miliárd dvojíc. Môj program ale nestihol dobehnúť počas otváracích hodín banky a ja som v banke nestihol nič nakúpiť ani predať.

Keď si Milošov sen vypočul Juraj, prišiel k nemu a povedal: „Miloš, to si urobil dosť neefektívne.” Miloš mu odpovedal: „Tak teraz to už viem. Celý súbor program musel prechádzať niekoľko tisíc krát, aby našiel všetky možné dvojice.”
Jurajova odpoveď na to bola: „Na to aby si našiel najvhodnejšiu dvojicu stačil iba jeden prechod súborom.”

 

Otázka:

Aký algoritmus mal Miloš napísať, aby jediným prechodom súboru našiel takú dvojicu, aby predstavovala najvýhodnejšiu dvojicu pre nákup a predaj danej akcie?

Súbor obsahuje ceny akcie chronologicky. Nezabudni na to, že nemôžeš akciu najprv predať a potom kúpiť.

Pre kontrolu svojho výsledku si stiahni súbor z tohto linku a nájdi svojou metódou optimálnu dvojicu pre predaj a nákup akcie. Pošli nám túto dvojicu cien. Pošli nám aj tvoj kód a algoritmus. Čísla v súbore sú z intervalu <0; 2^64) (typ unsigned long long int).

Ukážkový príklad:
Vstupný súbor: 30, 8, 20, 7, 18, 3
Nákup: 8
Predaj: 20

 

Úloha č. 5

Pri otvorení novej budovy internátu v Košiciach sa rozprávajú dvaja študenti. Jano: Počúvaj Mišo, tá budova je ale obrovská, veď ani nedovidím na vrchol. Má naozaj až 1000 poschodí? To sa z neho budú dobre vyhadzovať prázdne fľaše po žúrke. Mišo si predstaví zbierku prázdnych fliaš vo svojej starej izbe a vraví: Naše prázdne fľaše ale len tak nerozbiješ, možno ani z toho najvyššieho poschodia. Jano: Ale určite, skôr by ma zaujímalo, z ktorého najnižšieho poschodia sa už rozbije. Mišo: Nič jednoduchšie, tak to zistime.
Jano: No dobre, ale naše prázdne fľaše z minulého roka tu už predsa nemáme. Mišo: Žiadny problém, sme predsa pripravení na dnešnú žúrku, máme našťastie so sebou aspoň tieto dve. To predsa úplne stačí.  A bude nám na to stačiť len xx pokusov.

Otázka 1:
Ako budú Mišo s Janom postupovať pri zisťovaní z ktorého najnižšieho poschodia sa už fľaša rozbije, aby minimalizovali počet pokusov, ak môžu použiť len dve fľaše, ktoré majú pri sebe?

Otázka 2:
Aký by bol maximálny počet pokusov pri tejto stratégii v 1000 poschodovej budove?
Zapíšte aj príklad postupnosti poschodí, z ktorých budú Mišo s Janom púšťať fľaše pri tejto variante s maximálnym možným počtom pokusov.

 

 

 

Správne odpovede

 

Úloha č. 1

23. Vysvetlenie správnej odpovede nájdete na https://www.youtube.com/watch?v=USXHDNVYT14 

Úloha č. 2

Q1:

Správnych možností je viacero. Tu je jedna z nich:

Ukážem na strednú kartu a spýtam sa: Je karta vľavo so správnym heslom?

• Ak je odpoveď áno, vyberiem ľavú.
• Ak je odpoveď nie, vyberiem pravú.

V princípe môžu byť len 2 scenáre:

1. Ukážem na strednú kartu, ktorá je správna. Dostanem teda aj správnu odpoveď. Vyberiem teda kartu, pravú alebo ľavú, podľa odpovede.
2. Ukážem na strednú kartičku, ktorá je nesprávna. Dostanem teda nahodnú odpoveď. Vyberiem opäť kartičku podľa odpovede, teda pravú alebo ľavú. V tomto prípade je to úplne jedno, obidve majú správne heslo, pretože nesprávna karta je v strede.

Hlavná zásada teda je, ukázať na niektorú kartu a pýtať sa na správnosť (alebo nesprávnosť) inej karty. V závislosti na odpovedi vybrať potom pravú alebo ľavú kartu, nikdy nie tú, na ktorú ukazujem.

Uznali sme nakoniec aj nasledovné riešenie:

Ukázal by som na ľubovoľný papier a opýtal sa otázku:

Ak by som ukázal na papier s nesprávnym heslom, dostal by som správnu odpoveď?

Ak je heslo na zvolenom papieri správne, nebolo by možné na danú otázku odpovedať pravdivo?

Ak je heslo na papieri nesprávne, dostal by som akúkoľvek náhodnú odpoveď, teda heslo na zvyšných papieroch by bolo správne.

 

Q2:

Nie. Nie je možné prezradiť heslo ani kolegovi, aj keby vyriešil komplikovanú hádanku. Taktiež netreba zapisovať svoje heslá na papierik.

 

Q3:

Túto tretiu otázku sme nehodnotili bodovo, a teda nebolo možné za ňu získať body ani sa za ňu body neodpočítavali. Jedna zo zásad je- heslo nemá byť slovníkové. Slová, ktoré sú všeobecne známe a sú v slovníkoch, sú pri pokusoch o prelomenie prelomené ako prvé.

 

Úloha č. 3

Cinderella (Popoluška)

from string import ascii_letters
import random

cipher_letters = 'nzghqkcdmyfoialxevtswrupjbNZGHQKCDMYFOIALXEVTSWRUPJB'

def cipher(text):
trans = str.maketrans(ascii_letters, cipher_letters)
return text.translate(trans)

def decipher(text):
trans = str.maketrans(cipher_letters, ascii_letters)
return text.translate(trans)

if __name__ == '__main__':
#text_to_cipher = input('Text to cipher: ')

f = open("gutemberg.txt","r")
if f.mode =='r': text_to_cipher = f.read()
ciphered = cipher(text_to_cipher)

fd = open("gutemberg_d.txt","r")
if fd.mode =='r': text_to_decipher = fd.read()
deciphered = decipher(text_to_decipher)

print(f'Ciphered text: {ciphered}')
print('_____________________')
print(f'Deciphered text: {deciphered}')

 

 

Úloha č. 4

Kúpa:  1282018114205
Predaj:   18446743764542202088 

Správny algoritmus:

Pri algoritme sme hodnotili či bol dodržaný jednoprechodový cyklus a hlavne ako bola postavená logika vyhľadávania.

Optimálne hodnoty Kúpy a Predaja nepredstavujú minimálnu alebo maximálnu hodnotu. Hľadanie minima alebo maxima teda viedlo k nesprávnemu výsledku.

Riešení je samozrejme opäť viacero. Stačí napríklad dočasne uchovať minimum a dočasný najväčší zrealizovaný zisk a porovnávať každú následnú hodnotu zo súboru s týmito dvoma údajmi.

 

 

Úloha č. 5

Q1:

Najefektívnejšia stratégia je rozdeliť si celú budovu na časti: prvá (najnižšia) časť obsahuje "x" poschodí, druhá (nad ňou) "x-1" poschodí, tá nad ňou "x-2" poschodí, a tak ďalej.

Fľašu je najprv potrebné vyhodiť z "x"-tého poschodia. Ak sa fľaša rozbije, tak stačí už len maximálne "x-1" pokusov pod ňou na určenie, z ktorého poschodia sa fľaša rozbije.

Pri 1000-poschodovej budove, prvé poschodie z ktorého sa má hodiť prvá fľaša, zistíme nasledovne:

x+(x-1)+(x-2)+(x-3)+...+3+2+1>=1000

resp. 1+2+3+…+x, až kým súčet nepresiahne 1000.

V našom prípade x bude 45, lebo súčet 1+2+3+…+45 ako prvý prekročí 1000.

Prvý pokus je zo 45. poschodia.

2. pokus 45 + 44 = 89. poschodie,

3. pokus 89 + 43 =132. poschodie,

4. pokus 132 + 42 = 174,

5. pokus  174 + 41 = 215,

6. pokus  215 + 40 = 255,

…,

              + 11     =       980,

        +       10     =       990,

        +       9       =       999.

Pri rozbití fľaše sa Mišo s Janom musia vrátiť na predchádzajúce poschodie, kde sa flaša ešte nerozbila a postupovať po jednom poschodí.

Napr. pri rozbití fľaše na 999. poschodí sa vrátia na 991. poschodie a pokračujú takto: 991, 992, 993, …, 998.

 

Q2:

45

Pri tomto postupe je najhorší možný výsledok 45. Ak sa prvá fľaša rozbije na nižšom ako 999. poschodí, postupnosť ďalších poschodí bude síce iná ako je popísané vyššie, najhorší možný výsledok ale bude vždy 45.

Je potrebné si uvedomiť, že metóda delenia intervalov v tomto prípade nie je optimálna. Ak by sa pri prvom pokuse na poschodí 500 fľaša rozbila, prichádza do úvahy jedine možnosť pokračovať s poslednou fľašou z prvého poschodia až po najhoršiu alternatívu 449 po jednom. To nám dáva 500 pokusov. Toto riešenie bolo žiaľ najčastejšie z odpovedí.

 

PS: Fľaše našich študentov Miša a Jana boli v skutočnosti umelohmotné a bola v nich hroznová štava :)