Hello Codeforces,

Recently I came across a problem where we have to output the minimum number of fibonacci terms needed to make up a number. Repeating the terms to make up the representation is allowed. The fibonacci sequence 1,2,3,5,8,13,21.. will be used for all cases.

I can explain better with an example, lets say N=6, then the answer is 2, you can use the numbers 1 and 5 to make 6, another combination is 3 3, which also gives the optimal answer 2. However in this question we only need the minimum number of terms, not what those terms are.

Other examples: input = 5 output = 1 input = 7 output = 2 input = 19 output = 3

I tried out some examples and even submitted the greedy algorithm on this problem, which is to keep subtracting the largest fibonacci number possible which still keeps the result non-negative, and adding 1 for each of those terms subtracted. A few blogs on the same topic give this algorithm for solving the problem, however no proof on correctness.

A quick wikipedia search yielded Zuckendorf theorem, which just proves uniqueness with non-adjacent terms, I was unable to extend it to greedy or minimum.

Does anyone have a proof on correctness(or a counter-case is welcome too :D ) ?

Thank You Codeforces!