W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Ciąg liczb Fibonacciego to ciąg liczb całkowitych zdefiniowany rekurencyjnie w następujący sposób:
Początkowe elementy tego ciągu to: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Bajtazar bada, jak różne liczby można przedstawić jako sumy lub różnice liczb Fibonacciego. Aktualnie zastanawia się, jak daną dodatnią liczbę całkowitą przedstawić jako sumę lub różnicę jak najmniejszej liczby (niekoniecznie różnych) liczb Fibonacciego. Na przykład, liczby 10, 19, 17 i 1070 można przedstawić minimalnie, odpowiednio, za pomocą 2, 2, 3 lub 4 liczb Fibonacciego:
Pomóż Bajtazarowi! Napisz program, który dla danej dodatniej liczby całkowitej wyznaczy minimalną liczbę liczb Fibonacciego potrzebnych do przedstawienia liczby jako ich sumy lub różnicy.
W pierwszym wierszu standardowego wejścia znajduje się jedna dodatnia liczba całkowita () oznaczająca liczbę zapytań. W kolejnych wierszach będzie znajdowało się po jednej dodatniej liczbie całkowitej ().
Twój program powinien wypisać na standardowe wyjście dla każdego zapytania minimalną liczbę liczb Fibonacciego potrzebnych do przedstawienia liczby jako ich sumy lub różnicy.
Dla danych wejściowych:
1 1070
poprawną odpowiedzią jest:
4
Autor zadania: Karol Pokorski.