Buna dimineata!
Nu am mai rezolvat niciodata probleme in care se cer numarul de aranjamente posibile cu o anumita proprietate...nici nu stiu de unde sa incep. Imi puteti da niste indicatii de rezolvare a acestor gen de probleme?
Multumesc!
Exemplu de problema:
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).
Cerinţe
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 ieşire
Pe fiecare linie a fisierului de iesire soldati.out se va scrie un singur numar reprezentand numarul total de aranjamente posibile.
Restricţii şi precizări
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)
Timp de rulare/test: 1 secundă
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena