\begin{yl}{1}{Hoovi pühkimine}{luud}{1 sek}{20 punkti}
\emph{Idee: Ahto Truu, teostus ja lahenduse selgitus: Targo Tennisberg}

\begin{quote}
Leida, kuidas katta $M\times N$ ruudustik optimaalselt $1\times 3$ tükkidega. 
\end{quote}
Siin on kolm kvalitatiivselt erinevat varianti: ruudustik laiusega $1$, ruudustik laiusega $2$ ja laiemad ruudustikud.

Kui laius on $1$, saab pühkida algusest ruute kolmekaupa. Ruutude arv võib kas täpselt jaguda või siis võib $1$ või $2$ ruutu üle jääda.
Vastus on seega $\lceil M\times N \div 3\rceil$.

Kui laius on $2$, saab pühkida mõlemat rida algusest kolmekaupa. Ruutude arv võib kas täpselt jaguda või siis võib $1 \times 2$ või $2 \times 2$ ruutu üle jääda. Esimene juhtum on siin ülesandes ainuke tõeline erand, selle allesjäänud $1 \times 2$ ribakese katmiseks on vaja kaks korda luuda liigutada, sest nii kitsas kohas saab pühkida ainult pikkupidi.

Kui laius on $3$ või rohkem, saab pühkida kolme ruudu kaupa enamvähem igal viisil, kuni lõpuks jääb alles kas $1 \times 1$, $1 \times 2$ või $2 \times 2$ ala. Kuna aga hoovi laius on vähemalt $3$, on alati piisavalt ruumi see allesjäänud tükike vastavalt ühe või kahe luuavibutusega üle käia.

Seega on vastus alati $\lceil M\times N \div 3\rceil$, välja arvatud juhul, kui kogu ruudustik on mõõtmetega $2\times (3K+1)$, sellisel juhul on vastus ühe võrra suurem.

\end{yl}
