Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Michalovi Žabovi Anderlemu na [email protected]

V školskom bufete opäť dvihli ceny a vreckové vám nestačí ani na kúpu vašej obľúbenej sladkej maškrty. Nadišiel čas nájsť si brigádu! Pozreli ste si teda inzeráty v novinách a zaujala vás ponuka v “Továrni dláždení” – mzda slušná, podmienky prijateľné a riešenie PRASKu výhodou. Po krátkom pohovore ste boli razom prijatí.

Postavili ste sa k pásu, poblíž boli štyri škatule, v každej bolo neobmedzene veľa dlaždíc veľkostí \(1 \times 1\), \(2 \times 2\), \(3 \times 3\) a \(4 \times 4\). Asi ich budete baliť do menších zásielok… Po páse k vám však prišla iba obálka s listom, na ktorom bola napísaná nasledovná otázka: “Koľko existuje rôznych dláždení plochy \(4 \times 3\) pomocou dlaždíc \(1 \times 1\), \(2 \times 2\), \(3 \times 3\) a \(4 \times 4\)?”

Ostali ste zaskočení, pokrčili ste však plecami nad touto zvláštnosťou1 a pustili ste sa do práce. Rýchlo ste zistili, že hľadanou odpoveďou je 13. Na obrázku nižšie si môžete pozrieť štyri z týchto možností, zvyšné si môžete nakresliť sami. Na list ste teda napísali odpoveď, poslali ste ho ďalej a čakali na ďalšiu požiadavku.

Po prvom dni vám bolo jasné, že cieľom továrne je odpovedať na otázky o počte rôznych dlaždení plochy \(4 \times n\), výška dotazovanej plochy je vždy 4, pomocou spomenutých štyroch typov dlaždíc.

Úloha

  1. (2 body) Vypočítajte, koľko existuje rôznych možností dláždenia plochy \(4 \times 4\). Skúste stručne popísať, ako ste pri počítaní postupovali a prečo ste nevynechali žiadnu možnosť.

Pomerne rýchlo váš však táto práca omrzela a začali ste rozmýšľať, ako si ju uľahčiť. A veru ste vymysleli výborný trik. Jednoducho sa spýtate svojich kolegov! Samozrejme, nemôžete to spraviť priamo, lebo by vám určite nepomohli. Stačí ale, že spravíte list s požiadavkou a zamiešate ju medzi doručenú poštu. Potom si počkáte na odpoveď a bude. Má to však jeden háčik. Ak sa spýtate tú istú otázku ako prišla vám, bude to pôsobiť podozrivo. Pýtať sa teda môžete iba na menšie problémy.

Na riešenie zvyšných podúloh môžete využívať nasledovnú operáciu. Ak máte zistiť počet možností pre plochu \(4 \times n\), môžete sa spýtať ľubovoľne veľa otázok, ktoré sú typu “Koľko existuje rôznych dláždení plochy \(4 \times m\)?”, pričom musí platiť, že \(m\) je menšie ako \(n\). Následne predpokladajte, že na tieto otázky vám prišla správna odpoveď a takto získané odpovede môžete použiť na riešenie svojho problému.

  1. (2 body) Dostali ste mierne upravenú otázku: “Koľko existuje rôznych dláždení plochy \(4 \times n\) takých, že v poslednom stĺpci sa nachádzajú iba dlaždice \(1 \times 1\)?”. Popíšte spôsob, akým zistíte odpoveď na túto otázku s využitím vyššie uvedeného triku.

  2. (4 body) Popíšte postup, akým zistíte odpovede na nasledovné tri otázky:
    • Koľko existuje rôznych dláždení plochy \(4 \times n\) takých, že v poslednom stĺpci je aspoň jedna dlaždica \(2 \times 2\)?
    • Koľko existuje rôznych dláždení plochy \(4 \times n\) takých, že v poslednom stĺpci je aspoň jedna dlaždica \(3 \times 3\)?
    • Koľko existuje rôznych dláždení plochy \(4 \times n\) takých, že v poslednom stĺpci je aspoň jedna dlaždica \(4 \times 4\)?

  3. (2 body) Popíšte postup, ktorý použijete na odpovedanie otázky “Koľko existuje rôznych dláždení plochy \(4 \times n\)?”.

  4. (3 body) Po továrni sa rozniesol váš postup z podúlohy d), ktorý využívate na zjednodušenie práce. A samozrejme ho začali používať aj všetci vaši kolegovia. Väčšina správ v továrni je teraz od jej vlastných zamestancov. Vašou najnovšou úlohou je zistiť, koľko existuje dláždení plochy \(4 \times 7\). Nakreslite, ako bude prebiehať zisťovanie odpovede na túto otázku. Zaznačte všetky správy, ktoré bude v továrni poslané pre jej vyriešenie.

  5. (2 body) Pozorne si prezrite svoj obrázok z podúlohy e). Je takýto postup efektívny? Robí sa tam niečo navyše a ak áno, ako by ste to vedeli zlepšiť.

    V továrni je okrem iného aj obrovská korková tabuľa, na ktorú sa pripínajú rôzne odkazy a momentálne je prázdna. S kolegami by ste si chceli prácu ešte viac uľahčiť. Skúste navrhnúť spôsob akým môže fungovať odpovedanie na nové otázky tak, aby nikto z vás nerobil zbytočnú robotu.

  1. Kto potrebuje odpoveď na túto otázku?↩

Podúloha a)

Prvou úlohou bolo zistiť počet dláždení plochy \(4 \times 4\). Nie je ťažké si všetky takéto možnosti nakresliť. Ak si však chceme byť istý, že sme žiadnu možnosť nevynechali, je dobré postupovať systematicky. Jednou z možností je napríklad určiť si, akú najväčšiu dlaždičku v riešení použijeme.

Ak si povieme, že chceme použiť dlaždičku \(4\times 4\) máme práve jednu možnosť, pretože táto dlaždička pokryje celú požadovanú plochu. Nasledujú možnosti, ktoré využívajú dlaždičku \(3 \times 3\). Do plochy \(4 \times 4\) sa zmestí najviac jedna takáto dlaždička, môžeme ju však položiť na štyri rôzne miesta. Bez ohľadu na to, kam ju uložíme, budeme musieť zvyšok plochy vydláždiť pomocou \(1 \times 1\) dlaždičiek, na výber teda nemáme, dokopy sú to ďalšie 4 možnosti.

Ak chceme použiť dlaždičku \(2\times 2\) musíme si tieto možnosti ešte viac rozdeliť. Takýchto dlaždičiek sa totiž do plochy \(4\times 4\) zmestí viacero. Môžeme si teda určiť aj to, koľko takýchto dlaždičiek použijeme. Výhodou je, že keď tento zvolený počet dlaždičiek umiestnime, zvyšok môžeme pokryť už len pomocou dlaždičiek \(1 \times 1\), nebudeme teda musieť rozlišovať ďalšie možnosti, záleží len na tom, koľkými spôsobmi uložíme požadovaný počet dlaždíc \(2\time 2\).

Ak chceme položiť jednu dlaždicu \(2\times 2\) máme 9 možností – ľavý horný roh tejto dlaždice nemôže ísť do posledného riadku a stĺpcu. Pre dve dlaždice \(2 \times 2\) je týchto možností 16, tu neostáva nič iné ako si ich postupne všetky nakresliť. Pre tri dlaždice je možností 8, okrem tých kde vynecháme jeden z rohov ešte treba nezabudnúť aj na možnosti kde je jedna dlaždička v strede hrany. No a pri použití štyroch dlaždíc máme 1 možnosť.

Rovnako jednu možnosť máme aj vtedy, ak si povieme, že chceme využiť iba dlaždice veľkosti \(1 \times 1\). Dokopy sme teda napočítali \(1 + 4 + 9 + 16 + 8 + 1 + 1 = 40\) možností.

Podúloha b)

Našou úlohou je zistiť počet dláždení plochy \(4 \times n\) takých, že v poslednom stĺpci sa nachádzajú iba dlaždice \(1 \time 1\). Navyše môžeme využiť trik, v ktorom sa spýtame podobnú otázku našich spolupracovníkov v továrni. Jediné čo je potrebné je, aby sme sa spýtali na menšiu plochu.

Uvedomme si, že ak je povedané, že v poslednom stĺpci sú iba dlaždice \(1 \times 1\), je tento stĺpec jednoznačne určený. Navyše vôbec neovplyvňuje vyplnenie zvyšku plochy. Ostala nám teda plocha \(4 \times n-1\), ktorú môžeme vyplniť úplne ľubovoľne. Ku každému z týchto vyplnení potom už len stačí pridať posledný stĺpec plný dlaždíc \(1 \times 1\) a máme jedno z požadovaných vydláždení \(4\times n\). Naša úloha sa teda zmenila na to, že potrebujeme nájsť počet dláždení plochy \(4 \times (n-1)\). Ale práve toto vieme vyriešiť naším trikom, túto otázku jednoducho opäť pošleme do továrne a niekto to vypočíta za nás.

Na vyriešenie tejto úlohy je teda potrebné iba poslať továrni otázku “Koľko existuje rôznych dláždení plochy \(4 \times (n-1)\)”, počkať si na odpoveď, a potom to isté číslo použiť ako odpoveď na pôvodnú otázku.

Podúloha c)

Zdá sa, že táto podúloha bude veľmi podobná tej predchádzajúcej. A takmer tomu tak je, netreba sa však nechať pomýliť. Ak má byť v poslednom stĺpci dlaždica \(4 \times 4\) je to skutočne to isté. Je totiž len jediná možnosť ako tam túto dlaždicu uložiť. To čo nám ostane je navyše plocha \(4\times (n-4)\), na ktorej počet vyplnení sa vieme spýtať pomocou našeho triku.

Pri dlaždici \(3\times 3\) je to o niečo zložitejšie. Jednak sú dve možnosti kam ju vieme v poslednom stĺpci položiť. Navyše však to čo nám ostane nie je zarovnaná plocha veľkosti \(4 \times (n-3)\), buď nad alebo pod dlaždicou \(3 \times 3\) máme totiž tri prázdne miesta. Uvedomme si však, že na ne nič iné ako dlaždice \(1 \times 1\) ísť nemôžu. Po ich jednoznačnom vyplnení teda dostaneme plochu \(4 \times (n-3)\), na ktorej počet vydláždení sa môžeme spýtať cez trik. Tu však netreba zabudnúť, že odpoveď, ktorú dostaneme musíme ešte vynásobiť 2, lebo máme dve možnosti ako k nej pridať dlaždicu \(3\times 3\) a tri dlaždice \(1 \times 1\).

Aj pri dlaždici \(2\times 2\) to na prvý pohľad vyzerá jednoducho. Sú štyri možnosti ako vyplniť posledné dva stĺpce – jedna dlaždica \(2\times 2\) navrchu, v strede, naspodu alebo dve dlaždice – po ktorých vyplnení nám ostane plocha \(4 \times (n-2)\), na ktorú sa opýtame pomocou triku. Toto však nestačí, na nejaké možnosti totiž zabúdame.

Predstavme si, že dlaždicu \(2 \times 2\) dáme do posledného stĺpca navrch. Čo môže ísť pod ňu? Ďalšia dlaždica \(2\times 2\) alebo štyri dlaždice \(1\times 1\). Tieto možnosti sme však už zarátali. Okrem toho však môžeme dať dlaždice \(1\times 1\) iba do dvoch voľných políčok posledného stĺpca a vedľa nich uložiť ďalšiu dlaždicu \(2\times 2\). V tomto momente však máme aspoň čiastočne zaplnené tri stĺpce a možnosti vyplnenia \(4 \times (n-2)\) s touto možnosťou nepočítali. Musíme sa teda zamyslieť čo spraviť. Jedna možnosť je doplniť dve voľné políčka v treťom stĺpci dlaždicami \(1\times 1\), zistiť počet dláždení pre plochy \(4\times (n-3)\) a pridať to k možnostiam. Akurát ďalšou možnosťou je tam dať ďalšiu dlaždicu \(2\times 2\) a tým si problém posunúť o ďalší stĺpec.

V skutočnosti môžeme dlaždice \(2 \times 2\) pridávať takto na striedačku ľubovoľne dlho a vedie to k unikátnym možnostiam. V tomto prípade musíme teda započítať všetky tieto možnosti a opýtať sa výrazne viac otázok. Započítame totiž aj možnosti ktoré vzniknú z plochy \(4 \times 0\), teda keď iba budeme takto nastriedačku dávať dlaždice \(2\times 2\), možnosti pre plochy \(4 \times 1\), plochy \(4\times 2\) atď.

Označme si \(P(m)\) počet dláždení plochy \(4 \times m\). Potom odpoveďou na otázku “Koľko existuje rôznych dláždení plochy \(4\times n\) takých, že v poslednom stĺpci je aspoň jedna dlaždica \(2\times 2\)” je nasledovná hodnota:

\[4P(n-2) + 2(P(n-3) + P(n-4) + P(n-5) + \dots + P(1) + P(0))\]

Všimnite si krát dva, ktoré je tam kvôli symetrickosti týchto možností.

Podúloha d)

Táto podúloha sa už rieši ľahko, stačí spojiť to čo sme zistili v predchádzajúcich podúlohách. Všetky možné dláždenia plochy \(4 \times n\) totiž vieme rozdeliť na štyri skupiny podľa toho, aké dlaždice dáme do jej posledného stĺpca. A počet rôznych dlaždení pre každú z týchto skupín sme zisťovali v podúlohách b) a c), takže výsledkom tejto podúlohy je jednoducho ich súčet. Opäť, použijúc označenie \(P(n)\) pre počet dláždení plochy \(4\times n\), dostaneme výsledok

Podúloha e)

Našou úlohou je vypočítať ako bude prebiehať výpočet počtu dláždení pre plochu \(4 \times 7\) ak vyššie uvedený postup budú využívať všetci zamestnanci továrne. K tomu si však potrebujeme ujasniť niekoľko detailov posielania správ. Napríklad vo vzorci vyššie môžeme vidieť, že tie isté hodnoty potrebujeme vo vzorci viackrát. Nedáva však zmysel aby sme sa dvakrát pýtali na to, aká je odpoveď pre plochu \(4 \times 2\). Spýtame sa to len raz a potom zistenú hodnotu použijeme dvakrát.

Takisto, na niektoré jednoduché úlohy nepotrebujeme posielať správu, lebo odpoveď poznáme. Napríklad ak nám vyjde, že sa máme pýtať na počet dláždení plochy, ktorej veľkosť je záporná hodnota, takáto otázka zjavne nemá zmysel a jej odpoveďou je 0. V prípade plochy \(4 \times 0\) je odpoveď 1 – máme práve jednu možnosť ako vyplniť prázdnu plochu a to nespraviť nič. A rovnako pre plochu \(4 \times 1\) je len jedna možnosť – použitie dlaždíc \(1 \times 1\).

Dodržiac tieto pravidlá dostaneme nasledovný obrázok. Čísla v krúžkoch označujú veľkosť problému, ktorý sa akutálne rieši. Čierne čiary znázorňujú posielané správy. Červené čísla zase výsledok, ktorý je poslaný späť. Odpoveďou pre plochu \(4\times 7\) je teda 1029.

Podúloha f)

V skutočnosti existujú až dve zlepšenia, veľmi podobné, ktoré sa dajú zapracovať. Vo vzorovom riešení spomenieme obe, ale na získanie bodov stačilo ľubovoľné z nich.

Pri pohľade na obrázok vyššie by malo byť úplne jasné, čo sa robí zbytočne. Neustále dookola počítame tie isté čísla. Počet dláždení pre plochu \(4 \times 2\) počítame dokopy až 16 krát. Pritom odpoveď je zakaždým rovnaká a nezmení sa ani po stom počítaní. To by možno ešte nebol najväčší problém, lebo však vypočítať tie plochy \(4\times 2\) je ľahké. Problém je však pri väčších plochách. Lebo zakaždým keď napríklad počítame plochu \(4 \times 5\) nepridá sa nám jedno počítanie ale celá tá veľká časť podtým, teda 7 zbytočných výpočtov. A to už problém je.

Ako to teda vyriešiť? Použijeme korkovú tabuľu v továrni a jednoducho si na ňu budeme značiť už vypočítané hodnoty. Prvý zamestnanec, ktorý vypočíta počet dláždení plochy \(4\times m\) to zaznačí na tabuľu. Následne, každý zamestnanec, ktorý dostane za úlohu vypočítať počet dláždení plochy \(4 \times x\) sa najskôr pozrie, či už hodnota pre plochu \(4 \times x\) nie je na tabuli. Ak áno, jednoducho ju použije a ušetrí sebe aj zvyšným kopec práce. A ak tam nie je, tak ju začne počítať.

V reálnom svete ešte aj tu môže nastať problém. Čo ak začne naraz počítať hodnotu pre plochu \(4 \times m\) viacero ľudí. Hodnota ešte nie je na tabuli, lebo ju nikto nezistil, a preto na nej všetci začnú zbytočne pracovať. Potrebovali by sa preto dohodnúť, že prvý kto chce vypočítať plochu \(4 \times m\), zaznačí na tabuľu, že na tom pracuje. Ostatní by túto správu videli a počkali na výsledok.

Tento problém je však spôsobený len tým, že viacerí ľudia môžu počítať rôzne veci. V počítači, kde by sme túto techniku chceli použiť sa však môže vykonávať naraz najviac jeden výpočet (ak nezačneme operovať s viacjadrovými procesormi, ale o tom inokedy) a tento problém neexistuje.

Druhé vylepšenie je podobné a týka sa tej škaredej sumy \(2(P(n-3) + P(n-4) + \dots + P(1) + P(0))\), ktorá sa v našom vzorci vyskytuje. Spočítať viacero čísel dokopy je zdĺhavé, úmerne ich počtu, a toto počítanie tiež robí veľa ľudí opakovane. Na tabuľu si teda zamestnanci môžu značiť aj tieto súčty, ktorým sa ostatní určite potešia.

Ak by sme riešenie tejto úlohy naprogramovali, vyzeralo by nasledovne. Ak viete aspoň trochu programovať, pozrite sa ako elegantne sa to dalo riešiť a ako naša továreň predstavovala “rekurzívnu funkciu”. A ak sa s pojmom “rekurzia” stretnete niekedy v budúcnosti, skúste si pre lepšiu predstavu vybaviť továreň na dlaždičky :)

# -1 znamena, ze dana hodnota este nebola vypocitana
tabula_vysledky = [-1]*100
tabula_sucty = [1, 2]

# potrebujeme vypocitat pocet dlazdeni plochy 4xn
def tovaren(n):
    if n < 0:
        return 0
    if n < 2:
        return 1
    # niekto tuto ulohu pocital pred nami
    if tabula_vysledky[n] != -1:
        return tabula_vysledky[n]
    pocet = tovaren(n-1) + 4*tovaren(n-2) + 2*tovaren(n-3) + tovaren(n-4)
    if n-3 >= 0:
        pocet += 2*tabula_sucty[n-3]
    # vypocitame sucet prvych n hodnot
    tabula_sucty.append(tabula_sucty[-1] + pocet)
    # zapamatame si a posleme odpoved
    tabula_vysledky[n] = pocet
    return pocet

n = int(input())
print(tovaren(n))

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.