CSES - Lisäystavat

Tehtäväsi on selvittää, monessako eri järjestyksessä luvut 1n1 \dots n voidaan lisätä tyhjään binäärihakupuuhun siten, että puun korkeudesta tulee mahdollisimman pieni. Voit olettaa, että puussa on enintään 100 solmua.

Toteuta tiedostoon fillways.py funktio count, joka kertoo, monessako eri järjestyksessä luvut 1n1 \dots n voidaan lisätä binäärihakupuuhun halutulla tavalla.

def count(n):
    # TODO

if __name__ == "__main__":
    print(count(1)) # 1
    print(count(3)) # 2
    print(count(4)) # 16
    print(count(7)) # 80
    print(count(10)) # 253440
    print(count(31)) # 74836825861835980800000

Selitys: Jos n=3n = 3, kelvollisia järjestyksiä ovat vain [2,3,1][2,3,1] ja [2,1,3][2,1,3].