soldati
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: |
Timp maxim de executie: 0.1 secunde / test
Prof. Dana Lica
Colegiul Naţional "I.L.
Caragiale" Ploieşti
Contact: danal182001@yahoo.com