Prémia 1 - Vzorové riešenie
Zadanie
Máme mriežku, kde každé políčko má jednu z 5 farieb. V jednom ťahu si môžeme vybrať ľubovoľný súvislý útvar jednej farby, a prefarbiť ho na inú farbu (súvislé berieme, že sa políčka dotýkajú hranami). Vyfarbite celú mriežku na rovnakú farbu na čo najmenej ťahov. Na začiatku mriežka vyzerá takto:
Vzorové riešenie
Riešenie
Rovnakú farbu v celej mriežke dosiahneme tak, že si vyberieme začiatočný útvar (čiernym ohraničené modré otočené T-éčko) a budeme mu meniť farby na farby susedných útvarov, aby sa postupne zväčšoval ako sa k nemu budú susedné plochy pripájať.
Najprv zmeníme farbu začiatočného útvaru na bielu, následne na sivú, na modrú, žltú, sivú, žltú, červenú, sivú, bielu, žltú, modrú, sivú, červenú, bielu, modrú a nakoniec na žltú.
Pre lepšiu predstavu, rozširovanie našeho útvaru bude prebiehať tak, že po prvom prefarbení modrého T-éčka sa k našemu začiatočnemu útvaru pridružilo 6 susedných bielych políčok a vznikol nám tým útvar z 12 políčok, ktorý sme následne prefarbovali na sivú atď. Po 16-tom prefarbení je celá plocha už jednej farby v tomto prípade žltej.
Odpoveď: Celá mriežka sa dá zafarbiť na najmenej 16 ťahov.
Komentár
Veľa z vás išlo na tento príklad efektívnym spôsobom a to postupným prefarbovaním jedného útvaru. Riešenia sa potom líšili len podľa toho na aké farby ste prefarbovali v ktorom ťahu. Niekedy sme mali problém vo vašich riešeniach určiť, ktoré farebné označenia označujú ktoré farby zo zadania :)
Bodovanie
- 16 ťahov - 6 bodov
- 17 ťahov - 5 bodov
- 18 ťahov - 4 body
- 19 až 21 ťahov - 3 body
- 22 až 28 ťahov - 2 body
- 29 až 50 ťahov - 1 bod