Un copil are N soldati de jucarie, fiecare avand
ca inaltime un numar cuprins intre 1 si N, iar
soldatii au inaltimi distincte. Zi de zi, copilul aranjeaza cei N soldati in linie, dupa placul sau.
De curand, are o noua obsesie, si anume sa aranjeze cei N soldati astfel incat sa existe K secvente monotone in aranjament.
O secventa monotona este un sir de soldati aflati pe pozitii consecutive in
aranjament, iar inaltimea fiecarui soldat, mai putin primul din secventa, fiind
mai mare decat inaltimea soldatului aflat in stanga lui, secventa fiind maximala
cu aceasta proprietate (adica nu poate fi adaugat in secventa un soldat astfel
incat sa se pastreze ordinea crescatoare a inaltimilor). Spre exemplu,
pentru N=5 aranjamentul (3 5 1 2 4) este format din doua secventa monotone (3 5) si (1 2 4).
Cerinta
Determinati pentru N si K dat cate aranjamente posibile poate
face copilul.
Date de intrare
Pe prima linie a
fisierului text soldati.in se afla numerele naturale N si K.
Date de iesire
Pe fiecare linie a
fisierului de iesire soldati.out se va scrie un singur numar
reprezentand numarul total de aranjamente posibile.
Restrictii si precizari
§0
< K <= N <= 100
Exemplu
soldati.in
soldati.out
Explicatie
3
2
4
Cele 4
aranjamente cu 2 secvente monotone sunt: (1
3 2) (2 1 3) (2
3 1) (3 1 2)
Prof. Dana Lica Colegiul Naţional "I.L.
Caragiale" Ploieşti Contact: danal182001@yahoo.com