Saliutas

Taškai: 12

Du draugai bebrai gyvena savo pilyse, kurias skiria didelis miškas.

Jie kiekvieną vakarą siunčia vienas kitam žinutes, į dangų vieną po kitos leisdami fejerverko raketas.

Kiekviena žinutė sudaryta iš žodžių eilės.

Kiekvienas žodis yra koduojamas raketų seka.

Bebrai vartoja tik penkis skirtingus žodžius (žr. lentelę).

Pavyzdžiui, žinutei „Mediena Pilis Mediena“ išsiųsti būtų iššautas toks fejerverkas:

Pastebima, kad fejerverko kodai yra dviprasmiški. Fejerverkas galėtų reikšti taip pat ir „Medis Mediena“.

Žodis Raketų kodas
Pilis
Medis
Uola
Upė
Mediena

Kuri fejerverkų seka nėra dviprasmiška?

Linkėjimai Cezariui

Paaiškinimas

Daugelis informatikoje įprastų kodų visiems žodžiams, iš kurių sudarytos žinutės, skiria vienodą bitų skaičių. Tai didelis privalumas, nes iškoduoti paprasta, nevienareikšmiškumo negali būti. Atlikdami šią bebrų užduotį, turime dvi fejerverkų raketų rūšis – bitus 0 ir 1. Kad atskirtų vieną nuo kito penkis žodžius, kai žodžių kodų ilgis toks pat, draugams bebrams visada reiktų trijų raketų ((23=8) > 5). Tikriausiai jie labai dažnai vartoja žodį „Mediena“, žodžius „Pilis“ ir „Upė“ – rečiau, o žodį „Uola“ – labai retai. Todėl bebrai sugalvojo ekonomišką kodą, kuriuo sutaupo daug raketų. Protinga?
Būtų dar protingiau, jeigu būtų sugalvoję priešdėlinį kodą – tokį, kad iš pirmosios raketos (priešdėlio) būtų galima nustatyti po jo einančių raketų (bitų) skaičių, priklausančių tam pačiam žodžiui. Tada išvengtų daugiaprasmių žinučių ir galėtų sutaupyti šiek tiek raketų. Pavyzdys: Mediena = 01, Pilis = 00, Upė = 100, Medis = 101, Uola = 110. Čia pirmasis ženklas yra prefiksas. Jei 0, tai dviejų ženklų kodas, jei 1 – trijų.
Skirtingo ilgio kodai vartojami UTF-8 kodavime. Čia unikodo ženklai koduojami vienu arba keliais baitais.

Atsakymas

Teisingas atsakymas yra D.

Paeiliui bandome iškoduoti fejerverkų sekas, kol randame vienareikšmę. Pakanka sekoje rasti bent vieną papildomą reikšmę ir ją galima atmesti kaip netinkamą. Imkime seką A.

 
1 (Pilis) Pilis (Medis)  (Medis)  Medis
(Pilis) Pilis Mediena (Pilis) Pilis

Tam, kad neprasmuktų nepastebėta reikšmė, reikia bandyti sistemingai. Taikysime kodus iš eilės taip, kaip jie surašyti uždavinio lentelėje.
Gauname pirmąją reikšmę „Pilis Medis“, pažymėtą vienetu. Žodį rašome po paskutine jam priklausančia raketa, o po ankstesnėmis jam priklausančiomis raketomis rašome tą patį žodį skliaustuose.

Ieškome kitų reikšmių. Naują reikšmę bandome gauti iš jau esančios eilutės atmetę paskutinį žodį:
2            (Pilis)          Pilis

„Medis“ jau buvo, todėl lentelėje ieškome tinkamo po juo. Randame „Mediena“ ir prirašome prie antrosios eilutės:
2            (Pilis)          Pilis         Mediena

Liko dar dvi raketos. Jos laisvos, t. y. nesusietos su jau rastais žodžiais. Todėl naujo žodžio ieškome nuo lentelės pradžios. Randame „Pilis“ ir gauname antrą reikšmę.
2            (Pilis)          Pilis         Mediena   (Pilis)           Pilis

Taigi fejerverkų seka A netinka.

Analogiškai tikriname kitas fejerverkų sekas. Jeigu žodžių sekos nepavyks užbaigti – liks raketų seka, neatitinkanti jokio kodo, tai tada tą variantą reikia atmesti ir grįžti dar toliau į kairę.

 

 

 
Informacija atnaujinta 2015-12-03 07:50:57
Informuojame, kad nuo 2019 m. rugsėjo 2 d. Ugdymo plėtotės centro veiklas vykdo Nacionalinė švietimo agentūra. Ši interneto svetainė toliau nebus atnaujinama, tačiau visa informacija išliks aktyvi ir prieinama tol, kol bus perkelta į Nacionalinės švietimo agentūros interneto svetainę www.nsa.smm.lt.