Zadanie Rozkład Fibonacciego 2 etap XIX OI

Question

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!

Answer 1

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ć?

Comments

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

---

log_max, czyli wszystkie liczby fibonacciego nie przekraczające max_val

---

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

---

W sensie, pomysł taki:

ile_zostalo = N

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

?

---

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

---

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ć?

---

A nie jednak nie to nie zadziała

---

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

---

troszkę więcej?

---

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