Runda 4: Pochodzenie
27.10.2009 - Władysław Kwaśnicki
Limit czasowy: 5 sekund Każdy chciałby czuć się ważnym, a przynajmniej ważniejszym od innych... Z tego powodu obywatele Super Bogatego Państwa prześcigają się w wymyślaniu sposobów na okazanie swojej ważności. Ostatnimi czasy w modzie jest analizowanie drzew genealogicznych. Dla przykładu, jeśli twoim przodkiem jest Mieszko, który miał syna Bolesława, to możesz czuć się wyróżnionym. A jeśli do tego Bolesław miał syna Mieszka, to dopiero możesz chodzić z głową w chmurach. W naszym przypadku drzewo genealogiczne to spójny, acykliczny, nieskierowany graf T z jednym wyróżnionym wierzchołkiem, zwanym korzeniem. Każdy wierzchołek drzewa reprezentuje jedną osobę. Mając drzewo genealogiczne T możemy powiedzieć, że osobnik a jest SYNEM osobnika b, jeśli w drzewie T istnieje krawędź między a i b oraz a jest dalej od korzenia niż b. W naturalny sposób możemy powiedzieć, że b jest OJCEM a, jeśli a jest SYNEM b. Również w naturalny sposób możemy powiedzieć, że c jest POTOMKIEM a, jeśli c jest SYNEM a lub c ma OJCA b, który jest POTOMKIEM a.
Wzorzec f opisujemy podając ciąg a1 b1 a2 b2 .... bn-1 an, gdzie ai są to imiona kolejnych osobników, natomiast bi to albo SYN, albo POTOMEK. Wzorzec f można dopasować do drzewa T, jeśli każdemu elementowi ai można przyporządkować wierzchołek drzewa tak, że:
Dla przykładu wzorzec z pierwszego akapitu to: Mieszko SYN Bolesław SYN Mieszko.
WejściePierwsza linia wejścia zawiera liczbę naturalną N (1<=N<=105), oznaczającą liczbę osobników w drzewie genealogicznym. Następne N linii to opis drzewa genealogicznego. W pierwszej linii opisu znajduje się pojedyńcze słowo w — imię osobnika w korzeniu. W i-szej (i>1) linii opisu drzewa znajduje się liczba p oraz słowo w (1<=p<i), gdzie w to imię osobnika, a p to numer linii opisu drzewa, w którym znajduje się jego ojciec.
WyjścieW q kolejnych liniach wyjścia należy wypisać kolejne odpowiedzi na zapatynia. Odpowiedź na zapytanie to TAK albo NIE, w zależności od tego, czy dany wzorzec da się dopasować do drzewa genealogicznego. PrzykładDla danych wejściowych:
6 piotr 1 wladek 1 sylwia 3 pawel 4 alan 5 pawel 2 2 piotr POTOMEK sylwia 3 piotr SYN sylwia SYN alan
poprawną odpowiedzią jest:
TAK NIE
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto. |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com