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 SS ja merkille cc, kuinka monta sanaketjua sanoista SS voi muodostaa siten, että viimeinen merkki on cc.[/hint]

Laatoitus

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