Historyjka
W komunikatorze K, ze scentralizowanym serwerem, głównym zadaniem serwera jest rozwiązywanie nicków na adresy komputerów (ipv4+port) użytkowników. Ich komunikatory potem już łączą się ze sobą bez użycia serwera.
Serwer do obsługi zapytań korzysta wewnętrznie z drzewa BST (z porządkiem leksykograficznym względem nick'ów). Dzięki temu może w dowolnym momencie szybko dodać kolejnych użytkowników do systemu.
O kształcie drzewa BST decyduje kolejność zgłoszeń. Główni programiści zastanawiają się czy nie warto poczynić optymalizacji. W tym celu zostałaś/eś poproszona/y o dokonanie statystyk.
Problem
Mając dostępne logi ułożone w kolejności zgodnej z tą w jakiej użytkownicy pojawiali się w systemie, oraz ilość odpytań do o ich nicka w ostatnim miesiącu, określić jakie byłoby obciążenie wspomnianej struktury danych w zależności od sposobu konstrukcji drzewa.
Zbuduj trzy drzewa BST, podając elementy do operacji Insert():
-
TreeFromMin - w kolejności "od najmniejszej" ilości odpytań.
-
TreeAsInput - w kolejności zgodnej z danymi wejściowymi (czyli chronologią).
-
TreeFromMax - w kolejności "od największej" ilości odpytań.
W przypadku dwóch węzłów o tej samej ilości odpytań o kolejności decyduje porządek (odpowiednio do drzewa rosnący lub malejący) leksykograficzny nick’a.
Dla każdego drzewa policz ile w poprzednim miesiącu zostałoby odwiedzonych sumarycznie węzłów drzewa. Niech wyniki dla poszczególnych drzew będą FromMin, AsInput, FromMax.
Specyfikacja wejścia
Wiersze zawierają odpowiednio nick, adres ip+port, ilość odpytań z ostatniego miesiąca, oddzielone pojedynczym tabulatorem.
-
nick - do 16 znaków ze zbioru: a-z, A-Z, 0-9.
-
ip:port - cztery liczby <0;28-1> w zapisie dziesiętnym oddzielone kropką jako ip, a po nich dwukropek i numer portu <0; 216-1>
-
hits - ilość odwołań w ostatnim miesiącu <0;231-1>
Dane mogą być, ale nie muszą zakończone pustym wierszem. Dla każdego nick-a widnieje jeden wpis w logu. Sumaryczna ilość wierzy - n jest <1;1000000>.
Specyfikacja struktury
Komparator nicków w drzewie ma być zgodny z porządkiem leksykograficznym stosowanym przez komparator string w C++ na platformie testowej. (Więcej informacji w pliku komparator_cpp.html).
Specyfikacja wyjścia
Trzy linie, odpowiednio po trzy, dwie, jedną liczbę całkowitą.
W pierwszej linii odpowiednio trzy liczby:
-
FromMax AsInput FromMin
W drugiej, dwie różnice:
-
AsInput-FromMax FromMin-AsInput
W trzeciej, jedna różnica:
-
FromMin-FromMax
Porada implementacyjna
Przyjrzyj się na możliwe wielkości danych wejściowych i zastanów się nad odpowiednimi typami liczb do obliczeń arytmetycznych.
Limity
Pamięć: 400MB.
Przykłady
-
nicki i adresy ip:port osób zostały wymyślone, stąd możliwa zbieżność jest zupełnie przypadkowa
00.in
a 45.67.214.4:6723 10 b 56.25.67.123:12543 1000 d 56.23.78.213:3465 200 c 68.123.234.34:4343 1
00.out
1423 2614 3421 1191 807 1998
01.in
c 33.33.33.33:3333 3 i 99.99.99.99:9999 9 a 11.11.11.11:1111 1 d 44.44.44.44:4444 10 f 66.66.66.66:6666 5 b 22.22.22.22:2222 2 h 88.88.88.88:8888 8 g 77.77.77.77:7777 4 e 55.55.55.55:5555 7
01.out
145 178 261 33 83 116
02.in
a 45.67.214.4:6723 2147483645 h 23.213.23.56:3465 2147483640 e 73.158.223.142:3245 2147483643 b 56.25.67.123:12543 2147483647 g 26.63.28.123:6578 2147483641 d 56.23.78.213:3465 2147483646 c 68.123.234.34:4343 2147483644 f 67.23.435.123:2341 2147483642
02.out
55834574703 64424509310 73014443915 8589934607 8589934605 17179869212