Fişierul intrare/ieşire: | arbori2.in, arbori2.out | Sursă | utcn-2021 |
Autor | Tudor Muresan | Adăugată de | Ciprian Oprisa •cypry |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 16384 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arbori binari de căutare ordonați
Se consideră toţi arborii binari de căutare distincţi având noduri, cu cheile nodurilor de la la şi care au secvenţa de traversare INordine: . Se ordonează arborii de mai sus în ordinea lexicografică descrescătoare a secvenţelor de traversare PREordine. De exemplu pentru avem arborii de mai jos:
Se observă că toţi cei 14 arbori distincţi au secvenţa de traversare INordine iar secvenţele de traversare PREordine sunt în ordine lexicografică descrescatoare.
Fiind dată secvenţa de traversare PREordine a unui arbore de căutare definit mai sus se cere să se calculeze numărul de ordine al arborelui.
Date de intrare
Fişierul de intrare arbori2.in conţine mai multe exemple de test. Un exemplu are pe prima linie un întreg precizând numărul nodurilor arborelui binar de căutare (având cheile şi secventa de traversare INordine ). Pe linia următoare sunt întregi separaţi de un spaţiu reprezentând secvenţa cheilor obţinuta la traversarea PREordine a arborelui binar de căutare. Fişierul se termină cu o linie conţinând un 0.
Date de ieşire
Fişierul de ieşire arbori2.out conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte numărul exemplului de test urmat de ':' şi de numărul de ordine, luat modulo 9999991, al arborelui binar de căutare cu secvenţa cheilor la traversarea PREordine dată.
Restricţii
Exemplu
arbori2.in | arbori2.out |
---|---|
4 3 1 2 4 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 0 | 1:7 2:5583241 |
Precizări
Un arbore binar de căutare este un arbore binar ce satisface următoarele condiţii:
- subarborele stâng al unui nod conţine numai noduri cu chei mai mici decât cheia nodului
- subarborele drept al unui nod conţine numai noduri cu chei mai mari decât cheia nodului
- atât subarborele stâng al unui nod, cât şi cel drept sunt arbori binari de căutare
O traversare PREordine (Rădacină-Stânga-Dreapta) a arborelui tipăreşte cheia rădăcinii urmată de traversarea subarborelui stâng şi apoi a celui drept. O traversare INordine (Stânga-Rădacină-Dreapta) a arborelui tipăreşte subarborele stâng, apoi tipăreşte cheia rădăcinii şi la sfârşit subarborele drept. De exemplu traversarea arborelui de mai sus este:
- PREordine:
- INordine:
Două secvenţe de numere şi sunt ordonate lexicographic descrescător dacă:
- sau
- şi sau
- şi şi sau
- şi şi şi