1 / 4
Jul 2019

Gdy pisałem kod do tego zadania, zauważyłm że jest on bardzo zawiły. Uprościłem go, wprowadzając funkcje.
Sędzia zaakceptował zadanie, jednak chciałbym się dowiedzieć co jeszcze mogę zrobić, aby np. zwiększyć czytelność.
Link do zadania10
Link do Ideone11

  • created

    Jul '19
  • last reply

    Jul '19
  • 3

    replies

  • 606

    views

  • 3

    users

  • 2

    likes

  • 3

    links

Proszę, nie zadawaj pytań w dziale pl.spoj.com. Od tego masz działy Zbiór zadań lub Podstawy programowania. Możesz wejść w edycję tematu swojego pytania i zmienić dział na odpowiedni. Dotyczy to także twoich wcześniejszych pytań.

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/ntxkLI9