Fişierul intrare/ieşire:kcons.in, kcons.outSursăLot Vrancea 2010, Baraj 1
AutorAdrian Airinei, Cosmin GheorgheAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Kcons

Andrei este în mare dificultate: se pare că are câteva probleme la şcoală. Prietenii lui s-au decis să-l mai înveselească şi i-au propus spre rezolvare o problemă la care se gândeau de mai mult timp. Problema cere numărarea tuturor permutărilor cu N elemente care respectă următoarea proprietate: orice subsecvenţă pentru care elementele ei sunt atât în ordine crescătoare, cât şi consecutive are lungimea maxim K.

Deoarece Andrei este ocupat, ajutaţi-l să determine numărul de permutări cu proprietatea cerută, modulo 30013.

Date de intrare

Pe prima linie a fişierului de intrare kcons.in se vor afla două numere naturale N şi K având semnificaţiile din enunţ.

Date de ieşire

În fişierul de ieşire kcons.out veţi afişa un singur număr reprezentând numărul de permutări cu proprietatea cerută, modulo 30013.

Restricţii

  • 1 ≤ N ≤ 2000
  • 1 ≤ K ≤ N
  • Pentru 10% din teste N ≤ 10
  • Pentru 50% din teste N ≤ 70
  • Pentru 70% din teste N ≤ 300
  • Pentru 40% din teste K = 1

Exemplu

kcons.inkcons.outkcons.inkcons.out
4 2
21
25 10
27042

Explicaţie

Din cele 24 de permutări posibile următoarele trei nu sunt bune: 1 2 3 4, 2 3 4 1, 4 1 2 3. Subsecvenţele subliniate conţin numere crescătoare şi consecutive, iar lungimea lor este mai mare decât 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content