• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Rozkład Fibonacciego 2 etap XIX OI

VPS Starter Arubacloud
0 głosów
202 wizyt
pytanie zadane 16 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 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ź

0 głosów
odpowiedź 16 marca 2023 przez Whistleroosh Maniak (56,900 p.)
edycja 16 marca 2023 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 16 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Może robić takiego BFS-a? najpierw wrzucamy log(max_val) na kolejkę i dodajemy od jak największych?
komentarz 16 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
log_max, czyli wszystkie liczby fibonacciego nie przekraczające max_val
komentarz 16 marca 2023 przez Whistleroosh Maniak (56,900 p.)
Blisko. Czy konieczy jest BFS? Może wystarczy brać zachłannie?
komentarz 16 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

W sensie, pomysł taki:

ile_zostalo = N

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

?

komentarz 16 marca 2023 przez Whistleroosh Maniak (56,900 p.)
Tak, to zadziała. Da się to jakoś przenieść na wersję z odejmowaniem?
komentarz 16 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 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 16 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
A nie jednak nie to nie zadziała
komentarz 16 marca 2023 przez Whistleroosh Maniak (56,900 p.)
Hint: jeśli fib_i <= k < fib_{i+1} to rozwiązanie zawiera i lub i+1 liczbę Fibonacciego
komentarz 16 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
troszkę więcej?
komentarz 16 marca 2023 przez Whistleroosh Maniak (56,900 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

Podobne pytania

0 głosów
1 odpowiedź 154 wizyt
pytanie zadane 20 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...