2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Važiavimas dviračiu

Taškai: 12

Mieste atsirado naujas atrakcionas – važiavimas dviračiu specialia trasa. Kiekviena trasa turi keletą segmentų, kuriais galima važiuoti nuo kalvos, į kalvą arba lyguma. Kiekvienas segmentas sudarytas iš vienos ar daugiau vienodų sekcijų. Atrakciono taisyklės yra tokios:

  • Pradinis greitis yra 0 km/h.
  • Kiekvienoje sekcijoje, kuria važiuojama nuo kalvos, dviračio greitis automatiškai padidėja 10 km/h.
  • Kiekvienoje sekcijoje, kuria važiuojama į kalvą, dviračio greitis automatiškai sumažėja 10 km/h.
  • Kiekvienoje lygumos sekcijoje viskas priklauso nuo dviratininko: galima arba didinti, arba mažinti greitį 10 km/h.
  • Finišuojant dviračio greitis turi būti 0 km/h. Važiuojant trasa greitis gali sumažėti iki 0 km/h, bet tada jis turi būti nedelsiant padidintas – kitaip dviratis sustos!

Paveiksle pateikta schema trasos, įveikiamos pagal nurodytas taisykles. Lygumos sekcijose greitis didinamas arba mažinamas, kaip nurodyta apskritimuose (+ arba –). Kiekvienas kvadratas vaizduoja sekciją.

Čia pateiktos schemos trasų, kuriomis galima važiuoti. Tik viena iš šių trasų yra įveikiama pagal nurodytas taisykles. Kuri?

A. B.
C. D.

 

Paaiškinimas

Skliaustai yra gerai žinomi formaliosiose notacijose. Algebriniuose reiškiniuose, pavyzdžiui: [n(n–1)]/2 arba (a+b)(a–b), skliaustais išreikštai nurodomas operacijų atlikimo eiliškumas. Pastebėjote, kad skliaustai rašomi poromis – atidaromasis skliaustas ir uždaromasis skliaustas. Reiškiniai yra teisingi tik tada, kai kiekvieną atidaromąjį skliaustą atitinka uždaromasis skliaustas.

Panašiai daugelis notacijų (arba „kalbų“, kaip sako informatikai), skirtų „suprasti“ kompiuteriui, turi tam tikrų skliaustų. Pavyzdžiui, tinklalapio aprašo kalboje HTML pastraipa nurodoma atidaromosiomis ir uždaromosiomis gairėmis < p> ir </p>, o kiekviena gairė yra apskliaudžiama skliaustų pora < ir >. Kodėl įvairių skliaustų poros yra tokios populiarios kompiuterinėse kalbose? Priežastis yra paprasta – skliaustų poras paprasta apdoroti!

Dviračio trasos sekcijos taip pat gali būti laikomos skliaustais: važiavimo nuo kalvos sekcija yra atidaromasis skliaustas, važiavimo į kalvą sekcija yra uždaromasis skliaustas. Lygumos sekcija yra nežinomojo vieta, kurią reikia pakeisti arba atidaromuoju, arba uždaromuoju skliaustu. Dviračio trasa įveikiama, jei šis pakeitimas gali būti padarytas taip, kad rezultatas yra teisingas reiškinys su skliaustais. Sprendimo trasa C gali būti užrašoma taip: (?(??). Ji įveikiama, nes gali būti transformuota į teisingą reiškinį keliais būdais: ((())) arba ()(()), arba ()()(). Teorinėje informatikoje kalba su teisingais skliaustų reiškiniais vadinama Dyko kalba.

Raktiniai žodžiai: formaliosios kalbos, bekontekstės kalbos, Dyko kalba.

Atsakymas

C yra vienintelė įveikiama trasa. Lygumos sekcijose greitį galima didinti (+), mažinti (–), tada vėl mažinti (–) – taip greitis sumažėja iki nulio finišuojant. Kiti variantai: – + – arba – – +.

Kitos trasos neįveikiamos:

A trasa: net jei dviratininkas padidina greitį lygumos (antroje) sekcijoje, vis tiek sustoja po keturių sekcijų.

B trasa: net jei dviratininkas sumažina greitį abiejose lygumos sekcijose, priartėjus prie finišo greitis bus per didelis.

D trasa: paskutinėje sekcijoje dviračio greitis didėja. Kai greitėjama, greitis negali būti neigiamas, todėl neįmanoma, kad jis sumažėtų iki nulio prie finišo.