CSES - Peitteet

Tehtäväsi on laskea, monellako tavalla n×mn \times m suorakulmio voidaan peittää käyttämällä korkeintaan kk suorakulmiota. Kaikissa suorakulmioissa sivujen pituudet ovat kokonaislukuja.

Esimerkiksi 2×32 \times 3 suorakulmio voidaan peittää yhteensä 1313 tavalla, kun suorakulmioita saa käyttää korkeintaan 33:

Voit olettaa, että nn ja mm ovat välillä 141 \dots 4 ja kk on välillä 1nm1 \dots nm.

Python

Toteuta tiedostoon cover.py funktio count, joka antaa peittotapojen määrän.

def count(n, m, k):
    # TODO

if __name__ == "__main__":
    print(count(2,2,4)) # 8
    print(count(2,3,3)) # 13
    print(count(4,4,1)) # 1
    print(count(4,3,10)) # 3146
    print(count(4,4,16)) # 70878

Java

Toteuta tiedostoon Cover.java metodi count, joka antaa peittotapojen määrän.

public class Cover {
    public int count(int n, int m, int k) {
        // TODO
    }

    public static void main(String[] args) {
        Cover c = new Cover();
        System.out.println(c.count(2,2,4)); // 8
        System.out.println(c.count(2,3,3)); // 13
        System.out.println(c.count(4,4,1)); // 1
        System.out.println(c.count(4,3,10)); // 3146
        System.out.println(c.count(4,4,16)); // 70878
    }
}