CSES - Johdanto

Viikon 5 aiheena on eksponentiaaliset algoritmit. Tehtävät 1-3 käsittelevät eksponentiaalisia hakualgoritmeja ja tehtävät 5-6 dynaamista ohjelmointia osajoukoilla. KKKK luku 5 kertoo hakualgoritmeista ja luvusta 10, erityisesti kohdasta 10.4, on hyötyä tehtävissä 5-6.

Alla on vihjeitä tehtäviin. Kannattaa kuitenkin ensin miettiä ilman vihjettä. Vihjeen näet maalaamalla sen hiirellä.

Omenat

[hint]O(3^n) ratkaisu jossa kokeillaan kaikkia vaihtoehtoja on tarpeeksi nopea[/hint]

Kaverit

[hint]Kaikki valinnat voidaan saada lisäämällä uusi asukas johonkin toiseen valintaan[/hint]

Summa

[hint]KKKK 5.5[/hint]

Sanaketju

[hint]Laske jokaiselle sanojen osajoukolle S ja merkille c, kuinka monta sanaketjua sanoista S voi muodostaa siten, että viimeinen merkki on c.[/hint]

Laatoitus

[hint]Laske kaikille luvuille i \leq n ja m-pituisille bittijonoille B, kuinka monella tavalla voit laatoittaa i\times m-ruudukon 2\times 1- ja 1\times 2-laatoilla siten, että ainoastaan ne ruudukon alareunan kohdat joita vastaava bittijonon B bitti on 1 jäävät laatoittamatta.[/hint]