Prémia 1 - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Lúka pozostáva zo štvorčekovej siete 26\times 26. Nachádzajú sa na nej vlci (V) a ovce (O). Chcete na lúku vyhnať aj svojich 60 zvyšných oviec, no nechcete, aby ich zožrali vlci ani aby sa ovce pobili o trávu a preto musí platiť nasledovné:
  1. Na jednom políčku je vždy najviac jedno zviera.
  2. Všetky ovce musia byť v jednej oplotenej oblasti. Plot prechádza jedine po stranách štvorčekov a musí byť súvislý.
  3. Žiaden vlk nemôže byť v oplotenej oblasti.
  4. Aby sa ovce nepobili, každá môže mať na ôsmich políčkach okolo seba najviac jednu inú ovcu.

Rozostavte zvyšných 60 oviec a postavte plot tak, aby bol obvod plota čo najmenší. Ovcami, ktoré sú už na lúke, nemôžete hýbať.

Vzorové riešenie

Opravovali: miro
Riešenie

Najlepšie riešenie malo obvod lúky 144 hrán. Jeden spôsob opletenia je napríklad takýto (biele ovce sú zo zadania - tie sme neumiestňovali):

Komentár

Viacero z vás si zle prečítalo zadanie a na výslednom plániku ste mali umiestených 60 oviec namiesto 62. V takomto prípade sme za každú chýbajúcu ovcu pripočítali 5 hrán k celkovému obvodu.

Bodovanie
  • 145 a menej - 8 bodov
  • 146 až 147 - 7 bodov
  • 148 až 149 - 6 bodov
  • 150 až 151 - 5 bodov
  • 152 až 160 - 4 body
  • 161 až 170 - 3 body
  • 171 až 190 - 2 body
  • 191 až 250 - 1 bod
  • 251 a viac - 0 bodov