Zrobił ktoś to zadanko z drabinką w formie:
2 3
3 4
4 5
5 6
6 7
....
która dawała kolejne liczby Fibonacciego? Powinno to dać max koło 66 węzłów.

Standardowe podejście binarne z drabinką w formie:
2 3
4 5
4 5
6 7
6 7
....
lub:
2 3
3 -1
4 5
5 -1
6 7
7 -1
....
mi dało 88 węzłów w najgorszym przypadku (2^30-1-2^27).

Ja zrobiłem z ciągiem fibbonacciego, po jednym węźle na liczbę ciągu fib. (aż do największej mniejszej od 'k') + po dodatkowej na każdy zapalony bit w zapisie jako suma elementów ciągu fib.

Moje podejście "binarne" daje co najwyżej 60 węzłów (2*(log-1)+2) = 2*29+2.

2 3
3 (jeśli 1. bit zapalony, połącz z ostatnim wierzchołkiem; w przeciwnym wypadku -1)
4 5
5 (jeśli 2. bit zapalony, połącz z ostatnim wierzchołkiem; w przeciwnym wypadku -1)
7 8
8 (jeśli 3. bit zapalony, połącz z ostatnim wierzchołkiem; w przeciwnym wypadku -1)
...
itd.

Dla k = 5, dałoby to następujący graf
6
2 3
3 6
4 5
5 -1
6 -1
-1 -1

Binarnie można do 60 wierzchołków zjechać.

1 => 2 3
2 => 3 A
3 => 4 5
4 => 5 B
5 => 6 7
6 => 7 C

przy czym A, B, C to albo -1 (jeśli kolejna cyfra binarnego rozwinięcia k jest 0) albo n (jeśli ta cyfra to 1)

No tak, nie pomyślałem że te -1 w przypadku drugiej drabinki binarnej można wykorzystać i nie tworzyć dodatkowych węzłów :)

Wynik 60 (+- 1) można uzyskać analizując zapis k w systemie trójkowym:

k = 3 * x + r

Dla r = 0 lub 2

1 => 2 3
2 => 3 4
3 => 4 A

A = -1 dla r = 0 oraz A = n dla r = 2

Dla r = 1

1 => 2 4
2 => 3 4
3 => 4 n

Na swoje pocieszenie dodam że wzorcówka (outy w testach) też wykorzystywała tą gęstą drabinkę binarną i dała 87 dla testu 10d, gdzie moje rozwiązanie dało 86.

Ja zrobiłem tak samo jak Szymon. Dla 10d mam 52, a najwięcej dla 10a - 57.

Dodam jeszcze, że to zadanie wyjątkowo mi się podobało. Dziękuję i jednocześnie gratuluję autorowi :)

Dla mnie to było naciekawsze zadanie z serii C. Sporo kombinowania, a już się wpadnie na pomysł to się okazuje że kod mieści się na jednym ekranie.

Czyli jednak Fibonacci górą :)

Jeszcze pytanko do tych co robili Fibonaccim. Ile macie węzłów dla 969323028? Powinien to być najgorszy przypadek.

Ja mam 64.

W takim razie rzadka drabinka binarna wygrywa, daje najwięcej 60 (od 2^28+2^29=805306368 do 2^30=1073741824). Ma tą jeszcze zaletę że ilość węzłów jest niemalejąca przy rosnącym k.

Ciekaw jestem jeszcze jaki był najgorszy przypadek dla rozwiązania trójkowego Michała Miodka.

W rozwiązaniu trójkowym liczba węzłów też jest niemalejąca. Dla k = 10^9 wychodzi chyba dokładnie 59.

Ale co ciekawe, dla większych k drabinka trójkowa daje mniej węzłów.

Dla k = 10^18 mamy 116 węzłów w drabince trójkowej i 120 w binarnej.
Dla k = 10^100 mamy już 629 węzłów w trójkowej i 668 w binarnej.

To dowód wyższości liczby 3 nad 2 ;)

Jest chyba jeszcze lepiej: dla trójkowej drabinki mi wyszło n=57 dla k od 774840978=2*3^18 do 1162261466=3^19-1, czyli dla k=10^9 również.