Vai spēsi atrisināt šo uzdevumu, kuru 2019. gada Bebr[a]s konkursā risināja 11. un 12. klašu skolēni? Kā tas saistīts ar informātiku? Tas balstīts grafu teorijas principos.
Seši kaķi dodas uz peļu ballīti, lecot no salas uz salu. Kaķi var lēkt tikai uz blakus esošo salu. Viņi nevar lēkt pa diagonāli, kā arī uz vai pāri salām, kas ir zem ūdens.
Kaķis lec ļoti ātri, tāpēc varam uzskatīt, ka laiks, kas nepieciešams lēcienam, ir nulle. Pēc lēciena kaķis ir ļoti noguris, un tam ir nepieciešama atpūta, tāpēc kaķis paliek uz salas vienu minūti un tad atkal lec uz nākamo salu, ja tā nav jau aizņemta. Citādi kaķis paliek uz tās pašas salas vēl vienu minūti.
Kaķis var uzlēkt uz salas tikai tad, ja iepriekšējais kaķis dodas tālāk. Kaķi var sākt no jebkuras ar bultiņu norādītās salas.
Uzdevums
Cik minūtēs visi kaķi varēs nokļūt no sākumpunkta līdz galamērķim (ātrākajā variantā)?
Pareizā atbilde
Paturi kursoru virs Bebra attēla
un
uzzini atbildi!
Uzzini vairāk par konkursu Bebr[a]s lapā!