Drzewce

03.10.2010 - Michał Karpiński
TrudnośćTrudnośćTrudność

Zadania ze sprawdzaczką

Implementacje Drzewca...
C++, Java

Zadanie 1 - "Rotacje"

Podane jest drzewo BST. Zadaniem jest podanie wysokości tego drzewa po wykonaniu serii rotacji na ustalonych węzłach.

Wejście

W pierwszej linii podana jest jedna liczba $ N \in \langle 1,100000 \rangle $, która określa liczbę elementów w drzewie. W drugiej linii znajduję się $ N $ liczb $ x_1, x_2, \cdots , x_n $ oddzielonych spacjami. Ciąg $ \{x_1,x_2, \cdots, x_n\} $ jest permutacją zbioru $ \{1,2,3, \cdots , N\} $ i określa klucze oraz kolejność, w której elementy zostały wstawione do drzewa. W trzeciej linii podana jest liczba $ M \in \langle 0,1000 \rangle $ oznaczająca liczbę rotacji, którą wykonamy na drzewie. W kolejnej linii opisana jest seria rotacji w formie ciągu kluczy oddzielonych spacjami. Rotacje na podanych elementach należy wykonywać w kolejności od lewej do prawej.

Wyjście

Należy wypisać jedną liczbę oznaczającą wysokość drzewa BST po wykonaniu serii rotacji.

Przykład 1

Wejście:
5
1 2 3 4 5
1
3

Wyjście:
3

Przykład 2

Wejście:
7
4 2 1 3 6 5 7
5
5 3 3 2 1

Wyjście:
6

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com