Wyobraź sobie, że drabinka przedstawiona w zadaniu to drzewo. Oznaczmy wierzchołek zwycięzcy numerem 1. Jego wierzchołki potomne będą miały numery: 2 (w przypadku prawego czyli B) i 3 (w przypadku lewego czyli A). Uogólniając wierzchołek numer v ma dwa wierzchołki potomne o numerach: 2v (w przypadku prawego czyli B) i 2v + 1 (w przypadku lewego czyli A). Wystarczy zatem ustawić początkowy wierzchołek na 1 i przechodzić na odpowiednie wierzchołki w zależności od tego jaka litera jest na bieżącym wierzchołku. Dla przykładu: ABAAABB
v = 1, litera na indeksie n - 1 - v = 8 - 1 - 1 = B, a zatem v = 2v = 2
v = 2, litera na indeksie n - 1 - v = 8 - 1 - 2 = B, a zatem v = 2v = 4
v = 4, litera na indeksie n - 1 - v = 8 - 1 - 4 = A, a zatem v = 2v + 1 = 9
Wiemy, że całe drzewo ma 2n - 1 = 15 wierzchołków. Na ostatnim poziomie mamy 8 wierzchołków, na wcześniejszych 7 wierzchołków. W związku z tym 9 - 7 = 2, czyli naszą odpowiedzią jest 2 wierzchołek od prawej na ostatnim poziomie czyli 7.
Kod: http://ideone.com/ntxkLI
