Editorial for New Year's '17 P3 - Fibonacci Presents - Olympiads Online Judge

Editorial for New Year's '17 P3 - Fibonacci Presents

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The key observation to this problem is that a Fibonacci number is equal to the two before it: hence, instead of taking an item, you can take the two listed before it. Since you can only take $1$ $1$ of each item, there are only $\frac k 2$ $\frac{k}{2}$ combinations of Fibonacci numbers to try. There are some tricky edge cases in this problem: If $k>n+1$ $k > n + 1$ , then it is guaranteed to be impossible. In addition, since the first two items have equal masses of $1$ $1$ , whenever you would take the $2$ $2$ nd item, you can also take the first item.

Time Complexity: $\mathcal{O}(N)$ $O (N)$

Comments

There are no comments at the moment.