Fişierul intrare/ieşire:pviz.in, pviz.outSursăONI 2008, clasele 11-12
AutorAdrian DiaconuAdăugată desima_cotizoSima Cotizo sima_cotizo
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pviz

Fie N un numar natural nenul si P o permutare de lungime N a numerelor din multimea {1, 2, ..., N}. Definim un element vizibil in permutarea P ca fiind un numar Pi care are proprietatea ca Pj < Pi, oricare ar fi 1 ≤ j < i sau i=1.

Determinati numarul X de permutari de lungime N care au ca elemente vizibile exact M elemente date.

Date de intrare

Fisierul de intrare pviz.in contine pe prima linie doua numere naturale N si M, cu semnificatia din enunt, separate printr-un spatiu. A doua linie a fisierului contine M numere naturale distincte, ordonate crescator, separate prin cate un spatiu, reprezentand elementele vizibile.

Date de iesire

In fisierul de iesire pviz.out va contine o singura linie pe care va fi scris un numar natural reprezentand restul impartirii numarului X la 10 007.

Restrictii

  • 1 ≤ N ≤ 2000
  • 1 ≤ M ≤ N
  • Elementele vizibile sunt scrise in fisierul de intrare in ordine crescatoare.
  • Pentru 10% din teste N ≤ 10
  • Pentru 20% din teste N ≤ 14
  • Pentru 60% din teste N ≤ 375

Exemplu

pviz.inpviz.out
4 2
2 4
3

Explicatie

Sunt 3 permutari, de lungime 4, care au pe 2 si 4 ca elemente vizibile:
2 4 3 1
2 4 1 3
2 1 4 3
Permutarea 2 3 4 1 nu corespunde cerintei deoarece are ca elemente vizibile atat pe 2 si 4 cat si pe 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content