Rozkład Fibonacciego
Limit pamięci: 64 MB
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.
Wejście
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
(
).
Wyjście
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.
Przykład
Dla danych wejściowych:
1 1070
poprawną odpowiedzią jest:
4
Autor zadania: Karol Pokorski.