AlmostFibonacciKnapsack | Topcoder Archive

Problem Statement

You are given a sequence of integers. This sequence is defined as follows:

A[1] = 2
A[2] = 3
for each n >= 3, A[n] = A[n-1] + A[n-2] - 1

You are given a long x that is at least 2. Your task is to write x as a sum of distinct elements of the above sequence. More precisely, you have to find and return any valid int[] B with the following properties:

The elements of B are distinct positive integers.
x = A[B[0]] + A[B[1]] + ... + A[B[k-1]], where k is the number of elements in B.

If there are multiple solutions, return any of them. If there are no solutions, return the int[] {-1} instead.

Definition

Class:: AlmostFibonacciKnapsack
Method:: getIndices
Parameters:: long
Returns:: int[]
Method signature:: int[] getIndices(long x)
(be sure your method is public)

Constraints

x will be between 2 and 10^18, inclusive.

Examples

```
148
```
```
Returns: {6, 10, 8, 5 }
```
The first few terms of the sequence are 2,3,4,6,9,14,22,35,56,90. We can see that 14+90+35+9=148, and their respective indices are 6,10,8,5.
```
2
```
```
Returns: {1 }
```
```
13
```
```
Returns: {2, 3, 4 }
```
```
3
```
```
Returns: {2 }
```

86267769395

Returns: {3, 14, 15, 9, 26, 53, 5, 8 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.