2014 2015 2016 2017 2018

Liftas

Taškai: 12

Koridoriuje prie lifto sustatyti maišai. Ant kiekvieno maišo užrašytas jo svoris.

Koridorius siauras, todėl maišai kraunami į liftą iš eilės taip, kaip jie sustatyti. Kai tik sukrautų maišų svoris pasiekia 80 kg, bet neviršija 100 kg, liftas automatiškai įsijungia, nuveža krovinį ir vėl grįžta. Didesnio negu 100 kg svorio liftas negali vežti, todėl, prieš įkeliant kiekvieną maišą, tikrinama, ar krovinio svoris neviršys 100 kg. Jei viršys, maišas nustumiamas į koridoriaus galą ir bandoma įkelti kitą maišą.
Kai pradinėje eilėje maišų nebelieka, analogiški veiksmai atliekami su maišais, nustumtais į koridoriaus galą.

Tarkime, kad darbas baigtas – liftas nugabeno visus maišus, kurie į jį buvo kraunami aprašytu būdu.
Kuris teiginys teisingas?

A.    Antrąkart vežant krovinio svoris buvo 98 kg.
B.    Perstumti maišų į koridoriaus galą nereikėjo.
C.    Tik vieną kartą buvo nuvežtas lygiai 100 kg krovinys.
D.    Maišus liftas vežė penkiskart.

Paaiškinimas

Šiame uždavinyje reikia atkreipti dėmesį į algoritmą ir dėklo panaudojimą. Dėklas yra duomenų struktūra, į kurią paskutinis įdėtas duomuo išimamas pirmiausiai. Tą patį galima perfrazuoti ir atvirkščiai: pirmas įdėtas duomuo išimamas paskiausiai. Tai atitinka patarlę „kas pirmas į maišą, paskutinis iš maišo“. 
Kitas pavyzdys: ant virbo suverti šašlyko gabaliukai – numauti galima tik tą, kuris paskutinis buvo užmautas.
Pavyzdys iš informatikos. Interneto naršyklė aplankytų tinklalapių adresus deda į dėklą. Kai paspaudžiame grįžimo mygtuką, patenkame į paskiausiai prieš tai aplankytą tinklalapį.
Šiame uždavinyje dėklas buvo kuriamas iš į kitą koridoriaus galą nustumiamų maišų.

Dėklui priešinga duomenų struktūra vadinama eile. Į eilę sudėti duomenys išimami tokia pat tvarka, kokia buvo įdėti. Pirmas į eilę įdėtas bus pirmas ir išimamas. Taip ir žmonių eilėje prie kasos: pirmas į eilę atsistojęs pirmas ir aptarnaujamas.

Reikšminiai žodžiai: algoritmas, dėklas, struktūra.

Atsakymas

Teisingas atsakymas – C. 
Pirmuoju kėlimu pakraunami trys maišai, sveriantys 40 kg+20 kg+34 kg = 94 kg.
Antrą kartą į liftą pakraunamas pirmas, arčiausiai lifto esantis, maišas (55 kg). Jei įkeltume kitą iš eilės maišą (50 kg), krovinys viršytų leistiną svorį, todėl jis nustumiamas į priešingą koridoriaus galą. Į liftą įkeliamas kitas maišas (23 kg). Dabar lifte yra 55+23=78 kg. Dar per mažai. Imamas artimiausias maišas iš eilės (45 kg). Jis per sunkus, todėl nustumiamas į kitą koridoriaus galą. Tas pats atsitinka ir dar su vienu maišu (30 kg). Pagaliau eilėje laukiantis 10 kg maišas tinka ir liftas pakyla su 55+23+10 = 88 kg kroviniu.
Trečiasis kėlimas. Likę 3 maišai (25+30+15 = 70 kg) į liftą telpa, bet svorio dar trūksta. Maišų dar yra kitame koridoriaus gale (30, 45, 50 kg). Imamas arčiausiai lifto esantis maišas (30 kg). Gaunama lygiai 100 kilogramų (25+30+15+30 = 100 kg).
Ketvirtuoju kėlimu pakraunami likę du maišai (45+50 = 95 kg).
Matome, kad teisingas teiginys C, o kiti trys neteisingi.