Connection Status:
Competition Arena > AlmostFibonacciKnapsack

AlmostFibonacciKnapsack

SRM 687 · 2016-04-01 · by lg5293

SRM 687 · 2016-04-01 · by lg5293 · Math
Class Name: AlmostFibonacciKnapsack
Return Type: int[]
Method Name: getIndices
Arg Types: (long long)
Problem Statement

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.

Constraints

  • x will be between 2 and 10^18, inclusive.
Examples
0)
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.

1)
2
Returns: {1 }
2)
13
Returns: {2, 3, 4 }
3)
3
Returns: {2 }
4)
86267769395
Returns: {3, 14, 15, 9, 26, 53, 5, 8 }

Submissions are judged against all 120 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AlmostFibonacciKnapsack with a public method vector<int> getIndices(long long x) · 120 test cases · 2 s / 256 MB per case

Submitting as anonymous