Logowanie

Zadanie Rozkład Fibonacciego 2 etap XIX OI

pytanie zadane 6 dni temu w Algorytmy przez pasjonat_algorytmiki Stary wyjadacz (12,700 p.)

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/w1QbhPufazp-sH6X-u4pTnNu/site/?key=statement

Kompletnie nie wiem jak je zrobić w sensownej złożonności oprócz jakiegoś backtrackingu.

Z góry dziękuję za pomoc!

1 odpowiedź

odpowiedź 6 dni temu przez Whistleroosh Nałogowiec (46,920 p.)
edycja 6 dni temu przez Whistleroosh

To takie zadanie w którym trzeba zgadnąć rozwiązanie i sprawdzić np. brutem czy działa. Ja do teraz nie rozumiem dowodu dlaczego wzorcówka działa.

Jakie rozwiązanie nasuwa się w tym zadaniu? Możesz spróbować spojrzeć na prostszą wersję tego zadania, w której można tylko dodawać. Jak wtedy to zrobić?

komentarz 6 dni temu przez pasjonat_algorytmiki Stary wyjadacz (12,700 p.)

Może robić takiego BFS-a? najpierw wrzucamy log(max_val) na kolejkę i dodajemy od jak największych?

komentarz 6 dni temu przez pasjonat_algorytmiki Stary wyjadacz (12,700 p.)

log_max, czyli wszystkie liczby fibonacciego nie przekraczające max_val

komentarz 6 dni temu przez Whistleroosh Nałogowiec (46,920 p.)

Blisko. Czy konieczy jest BFS? Może wystarczy brać zachłannie?

komentarz 6 dni temu przez pasjonat_algorytmiki Stary wyjadacz (12,700 p.)

W sensie, pomysł taki:

ile_zostalo = N

while(ile_zostalo > 0)
{
biorę największą jaką mogę i ją odejmuję
}

?

komentarz 6 dni temu przez Whistleroosh Nałogowiec (46,920 p.)

Tak, to zadziała. Da się to jakoś przenieść na wersję z odejmowaniem?

komentarz 6 dni temu przez pasjonat_algorytmiki Stary wyjadacz (12,700 p.)

Zachłannie dodajemy aż nie przekroczymy, a jak przekroczymy to zachłannie odejmujemy, a ile można zachłannie dodać / odjąć w danym momencie możemy zrobić, napełniając vector liczb fibonnaciego nie przekraczających max_val i binarne szukać?

komentarz 6 dni temu przez pasjonat_algorytmiki Stary wyjadacz (12,700 p.)

A nie jednak nie to nie zadziała

komentarz 6 dni temu przez Whistleroosh Nałogowiec (46,920 p.)

Hint: jeśli fib_i <= k < fib_{i+1} to rozwiązanie zawiera i lub i+1 liczbę Fibonacciego

komentarz 6 dni temu przez pasjonat_algorytmiki Stary wyjadacz (12,700 p.)

troszkę więcej?

komentarz 6 dni temu przez Whistleroosh Nałogowiec (46,920 p.)

Spójrz na fib_{i+1}-k i k-fib_i Czy da się stwierdzić która liczba ma mniejszą dekompozycje? To cięzko sprawdzić ręcznie, lepiej napisać program który to przetestuje

...