CSES - Esitystavat

Monellako tavalla kokonaisluku nn voidaan esittää positiivisten kokonaislukujen summana? Kaksi tapaa ovat erilaiset, jos summat eroavat, kun luvut järjestetään pienimmästä suurimpaan. Summassa voi olla myös vain yksi luku.

Esimerkiksi luku 55 voidaan esittää seuraavilla tavoilla: 55, 1+41+4, 2+32+3, 1+1+31+1+3, 1+2+21+2+2, 1+1+1+21+1+1+2 ja 1+1+1+1+11+1+1+1+1.

Voit olettaa, että nn on välillä 1501 \dots 50. Koodisi tulee laskea vastaus itse (eli siinä ei saa olla esimerkiksi listaa, jossa on valmiit vastaukset joka testiin).

Python

Toteuta tiedostoon number.py funktio count, joka antaa esitystapojen määrän.

def count(n):
    # TODO

if __name__ == "__main__":
    print(count(4)) # 5
    print(count(5)) # 7
    print(count(8)) # 22
    print(count(42)) # 53174

Java

Toteuta tiedostoon Number.java metodi count, joka antaa esitystapojen määrän.

public class Number {
    public int count(int n) {
        // TODO
    }

    public static void main(String[] args) {
        Number n = new Number();
        System.out.println(n.count(4)); // 5
        System.out.println(n.count(5)); // 7
        System.out.println(n.count(8)); // 22
        System.out.println(n.count(42)); // 53174
    }
}