2014 2015 2016 2017 2018

Tiltų planavimas

Taškai: 9

Senelis bebras bijo vandens. Jis nori lankyti giminaičius iš savo gyvenvietės eidamas tiltais. Bebriukas labai myli senelį ir nori tiltais sujungti visas gyvenvietes. Tiltus jis tiesia laikydamasis šių dviejų taisyklių:
•    senelis bebras iš savo gyvenvietės bet kurią kitą gyvenvietę pasiekia ne daugiau kaip dviem tiltais;
•    bet kurioje gyvenvietėje turi prasidėti ne daugiau kaip du nauji tiltai.
Bebriukas pradeda planuoti. Gyvenvietes pažymi skrituliais. Senelio gyvenvietę pažymi raudonai, iš jos nutiesia pirmąjį tiltą. O kas toliau? Padėkite bebriukui.
Yra daug teisingų sprendimų. Bet kuriuo atveju reikės nutiesti dar penkis tiltus. Spustelėkite gyvenvietę ir tempkite tiltą link kitos gyvenvietės – tarp jų atsiras tiltas. Jei norite pašalinti tiltą, spustelėkite jį.

Paaiškinimas

Informatikoje daugelio algoritmų, realizuojančių medžio veiksmus, sudėtingumas priklauso nuo to medžio aukščio, todėl siekiame, kad didėjant medžio viršūnių skaičiui jo aukštis didėtų kiek galima lėčiau. Vadinasi, reikia derinti medžio kairįjį ir dešinįjį pomedžius.
Dvejetainis medis, kurio kiekvieno elemento kairiojo ir dešiniojo pomedžių elementų skaičiai skiriasi ne daugiau kaip vienetu, vadinamas visiškai subalansuotu medžiu.
https://lt.wikipedia.org/wiki/Medis_(duomen%C5%B3_strukt%C5%ABra)

Reikšminiai žodžiai: medis, dvejetainis subalansuotas medis, pomedis.

Atsakymas

Galimi du sprendimo būdai. 

Šis sprendimas atitinka dvi sąlygas: iš raudonai pažymėtos gyvenvietės kitą gyvenvietę galima pasiekti ne daugiau kaip dviem tiltais ir bet kurioje gyvenvietėje yra du nauji tiltai.

Tokias sąlygas atitinka ir šis planas:

Interaktyvi užduotis