Fişierul intrare/ieşire:countbst.in, countbst.outSursăLot Seniori Tulcea 2018, baraj 2
AutorMarian DariusAdăugată deTiberiu02Tiberiu Musat Tiberiu02
Timp execuţie pe test3 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Countbst

Un arbore binar este un arbore cu rădăcină în care fiecare nod are maxim 2 fii. Un arbore binar de căutare (Binary Search Tree) este un arbore binar în care fiecare nod are asociată o valoare, iar valoarea unui nod este strict mai mare decât toate valorile din subarborele său stâng şi strict mai mică decât toate valorile din subarborele său drept. Un exemplu de arbore binar de căutare este cel din stânga iar unul greşit în dreapta (deoarece 9 se află în subarborele stâng al lui 5 şi 3).

Cerinţă

Cunoscând numerele naturale N, K şi un şir A1, A2, ...AK cu toate elementele numere naturale distincte nenule mai mici sau egale cu N, vi se cere să număraţi câţi arbori binari de căutare există cu N noduri având valorile asociate nodurilor 1, 2, ... N (în orice ordine validă), astfel încât şirul A1, A2, ...AK să formeze un lanţ în arbore în această ordine. De exemplu, pentru N=8, K=5, A=(6, 7, 5, 3, 4), arborele de mai sus din stânga este unul valid.

Date de intrare

Fişierul de intrare countbst.in va conţine pe prima linie un număr natural T (numărul de teste), urmat de T teste. Fiecare test va fi descris prin două linii:

  • Pe prima linie se vor găsi două numere naturale N şi K separate printr-un spaţiu.
  • Pe linia a doua se vor găsi cele K numere naturale nenule distincte A1, A2, ...AK separate şi urmate de un spaţiu

Date de ieşire

În fişierul de ieşire countbst.out va conţine răspunsurile pentru fiecare dintre cele T teste, câte unul pe linie: numărul de arbori binari de căutare ce conţin şirul de K numere ca lanţ, afişat modulo 1 000 000 007 în ordinea testelor din fişierul de intrare.

Restricţii

Problema va fi punctată în baza următoarelor sub-probleme:

Grupă de testePunctajLimită NLimită KLimită T
13 puncteN ≤ 12k ≤ NT ≤ 10
24 puncteN ≤ 200k ≤ NT ≤ 10
37 puncteN ≤ 2.000k ≤ NT ≤ 10
45 puncteN ≤ 50∑k ≤ 2.000T ≤ 2.000
56 puncteN ≤ 200∑k ≤ 2.000T ≤ 2.000
67 puncteN ≤ 2.000∑k ≤ 2.000T ≤ 2.000
78 puncteN ≤ 500.000∑k ≤ 2.000T ≤ 2.000
8,9,103*3p=9 puncteN ≤ 2.000∑k ≤ 200.000T ≤ 200.000
1150 puncteN ≤ 500.000∑k ≤ 200.000T ≤ 200.000
121 punctN ≤ 3.000.000∑k ≤ 200.000T ≤ 200.000

Exemplu

countbst.incountbst.outExplicaţie
2
10 3
2 7 5
10 5
1 7 4 6 2
84
0
Pentru primul test avem 84 arbori binari de căutare cu nodurile 1,2, … , 10 care conţin lanţul (2,7,5).
Pentru al doilea test, nu există niciun arbore binar de căutare valid
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?