Statistics

Problem Statement for "AlmostFibonacciKnapsack"

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

  1. 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. 2

    Returns: {1 }

  3. 13

    Returns: {2, 3, 4 }

  4. 3

    Returns: {2 }

  5. 86267769395

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

  6. 323851819600013954

    Returns: {84, 81, 74, 71, 69, 66, 61, 58, 55, 49, 47, 45, 41, 32, 30, 28, 24, 21, 17, 11, 9, 6, 3, 2 }

  7. 506310719839645698

    Returns: {85, 81, 79, 73, 67, 63, 60, 58, 55, 52, 49, 46, 42, 40, 37, 34, 30, 26, 24, 20, 18, 16, 13, 11, 8, 4, 3 }

  8. 888728782244155778

    Returns: {86, 83, 80, 77, 73, 69, 62, 58, 54, 50, 48, 39, 36, 34, 29, 24, 20, 18, 11, 7, 2, 1 }

  9. 356163634378532610

    Returns: {84, 81, 79, 77, 74, 71, 69, 57, 55, 52, 50, 44, 42, 39, 31, 28, 24, 19, 14, 12, 8, 2, 1 }

  10. 400820820600226818

    Returns: {84, 82, 80, 75, 71, 68, 62, 59, 57, 53, 51, 49, 45, 39, 37, 33, 30, 26, 23, 18, 15, 13, 10, 1 }

  11. 845944887914908290

    Returns: {86, 83, 76, 64, 62, 57, 55, 53, 51, 47, 42, 34, 29, 27, 25, 20, 14, 10, 7, 4 }

  12. 115254914215817138

    Returns: {82, 78, 73, 69, 67, 64, 59, 57, 55, 53, 50, 45, 41, 36, 34, 31, 29, 26, 16, 11, 8, 6, 1 }

  13. 574837152164616514

    Returns: {85, 82, 80, 78, 74, 72, 68, 66, 61, 53, 47, 45, 43, 41, 39, 34, 29, 25, 23, 20, 18, 16, 14, 9, 7, 4, 3 }

  14. 385117062364349314

    Returns: {84, 82, 79, 74, 71, 69, 62, 60, 56, 54, 52, 50, 48, 46, 43, 38, 34, 32, 27, 25, 23, 21, 19, 13, 10, 6, 3 }

  15. 684505568877867650

    Returns: {86, 75, 72, 70, 67, 62, 60, 58, 54, 49, 47, 40, 36, 34, 30, 28, 26, 23, 21, 19, 15, 13, 11, 6, 3 }

  16. 307202240389644418

    Returns: {84, 80, 77, 71, 68, 66, 63, 59, 52, 47, 44, 42, 40, 38, 36, 32, 30, 27, 22, 17, 10 }

  17. 148226595308823778

    Returns: {82, 80, 77, 74, 67, 63, 60, 58, 47, 42, 38, 34, 31, 28, 23, 19, 13, 9, 4, 3 }

  18. 599627463558337282

    Returns: {85, 83, 78, 75, 72, 69, 66, 51, 46, 43, 39, 37, 33, 30, 28, 22, 19, 15, 11, 7, 3 }

  19. 318441859719317506

    Returns: {84, 80, 78, 76, 72, 66, 61, 58, 56, 54, 51, 49, 47, 43, 38, 35, 29, 20, 15, 10, 5 }

  20. 276487643092660834

    Returns: {84, 78, 74, 69, 64, 57, 54, 51, 46, 39, 34, 31, 29, 27, 21, 16, 14, 9, 5, 1 }

  21. 437606001880950338

    Returns: {85, 78, 74, 72, 64, 59, 57, 54, 52, 50, 47, 44, 41, 38, 31, 29, 27, 19, 17, 14, 13 }

  22. 94253921180226466

    Returns: {81, 79, 77, 71, 67, 63, 61, 58, 54, 52, 49, 47, 41, 38, 35, 31, 28, 23, 21, 19, 17, 13, 9, 1 }

  23. 185852896735932322

    Returns: {83, 79, 73, 71, 68, 63, 60, 58, 55, 53, 51, 49, 45, 43, 39, 36, 27, 24, 17, 14, 10, 8, 5, 3 }

  24. 213275478826658882

    Returns: {83, 80, 78, 70, 67, 65, 61, 57, 55, 47, 43, 41, 38, 35, 33, 31, 27, 24, 20, 18, 15, 10, 7, 4, 3 }

  25. 323933340713751554

    Returns: {84, 81, 74, 72, 63, 60, 57, 55, 53, 51, 44, 36, 34, 32, 28, 19, 15, 12, 7 }

  26. 351216252203853762

    Returns: {84, 81, 79, 76, 72, 70, 68, 65, 62, 60, 58, 55, 50, 47, 45, 43, 37, 35, 33, 31, 27, 20, 17, 5, 2 }

  27. 685803566750866306

    Returns: {86, 76, 70, 67, 60, 57, 53, 50, 44, 42, 40, 37, 33, 29, 26, 23, 20, 16, 14, 7, 5, 1 }

  28. 849822648258848770

    Returns: {86, 83, 77, 70, 68, 66, 63, 61, 57, 51, 48, 44, 40, 38, 36, 32, 28, 25, 22, 19, 17, 15, 7, 1 }

  29. 42520902587510514

    Returns: {80, 75, 72, 70, 67, 65, 55, 52, 50, 47, 45, 43, 41, 37, 30, 28, 24, 22, 18, 16, 14, 12, 9, 7, 4, 1 }

  30. 368994927952122754

    Returns: {84, 82, 77, 72, 70, 66, 57, 52, 49, 46, 43, 39, 36, 34, 27, 23, 21, 18, 15, 13, 9, 1 }

  31. 73706262430787714

    Returns: {81, 77, 75, 65, 63, 58, 55, 51, 49, 47, 44, 42, 40, 34, 29, 20, 14, 12, 6, 5 }

  32. 340259359616967874

    Returns: {84, 81, 78, 75, 73, 66, 64, 59, 57, 52, 48, 39, 37, 34, 25, 22, 20, 16, 12, 8, 2, 1 }

  33. 986364943334026626

    Returns: {86, 84, 80, 76, 74, 72, 70, 68, 63, 61, 59, 57, 55, 51, 49, 45, 38, 34, 32, 30, 24, 19, 16, 14, 9, 7, 4, 3 }

  34. 223577617493963778

    Returns: {83, 81, 73, 70, 68, 65, 63, 59, 56, 54, 51, 48, 43, 41, 36, 33, 31, 26, 22, 19, 16, 10, 8, 4, 1 }

  35. 370543211593236354

    Returns: {84, 82, 77, 74, 71, 67, 64, 62, 59, 56, 54, 50, 47, 44, 40, 37, 35, 33, 31, 25, 19, 11, 6, 2 }

  36. 25769853554291178

    Returns: {79, 74, 69, 66, 61, 59, 57, 53, 50, 46, 41, 39, 37, 35, 32, 26, 24, 22, 19, 17, 15, 12, 10, 7, 2 }

  37. 99991576830575586

    Returns: {82, 71, 69, 67, 65, 62, 57, 55, 44, 39, 36, 34, 32, 26, 24, 22, 20, 18, 16, 14, 11, 8, 3 }

  38. 355086483184020930

    Returns: {84, 81, 79, 77, 73, 70, 67, 65, 62, 60, 58, 56, 54, 49, 46, 43, 40, 38, 36, 33, 31, 28, 24, 20, 14, 10, 8, 4, 1 }

  39. 412180801378569730

    Returns: {84, 82, 80, 78, 72, 68, 61, 57, 55, 42, 38, 36, 34, 32, 19, 17, 5 }

  40. 544675825706107714

    Returns: {85, 82, 79, 73, 71, 66, 64, 60, 52, 48, 43, 40, 36, 34, 30, 28, 25, 21, 19, 14, 11, 8, 3 }

  41. 439776964220680450

    Returns: {85, 78, 75, 73, 70, 67, 61, 59, 57, 53, 45, 40, 34, 32, 30, 28, 25, 22, 20, 12, 10, 8, 5, 1 }

  42. 508527825426690370

    Returns: {85, 81, 79, 75, 69, 59, 57, 54, 51, 47, 45, 37, 30, 28, 24, 20, 17, 15, 10, 8, 2, 1 }

  43. 134753555818367570

    Returns: {82, 79, 77, 74, 72, 69, 67, 63, 61, 59, 55, 50, 47, 44, 41, 39, 30, 28, 26, 22, 19, 14, 12, 9, 7, 5, 1 }

  44. 68215485903652338

    Returns: {81, 76, 73, 67, 61, 48, 45, 39, 35, 32, 28, 24, 19, 16, 14, 7, 5, 1 }

  45. 712051544593628418

    Returns: {86, 79, 76, 74, 72, 69, 67, 65, 61, 59, 57, 54, 49, 40, 38, 35, 32, 29, 27, 23, 20, 12, 9, 7, 4 }

  46. 469319655759492866

    Returns: {85, 80, 77, 74, 68, 66, 63, 61, 58, 55, 53, 50, 47, 44, 42, 39, 35, 33, 30, 28, 26, 22, 14, 8 }

  47. 943072127254054018

    Returns: {86, 84, 75, 66, 64, 61, 59, 57, 55, 47, 45, 41, 36, 33, 31, 28, 26, 23, 20, 18, 12, 9, 5, 3 }

  48. 795348719600481154

    Returns: {86, 82, 78, 73, 70, 68, 66, 63, 60, 58, 54, 51, 47, 40, 32, 29, 27, 23, 21, 19, 17, 15, 12, 9, 2 }

  49. 116899984546079970

    Returns: {82, 78, 74, 72, 70, 62, 54, 51, 47, 42, 37, 33, 31, 29, 25, 22, 20, 18, 12, 8, 5, 2 }

  50. 477416668560168642

    Returns: {85, 80, 78, 75, 73, 68, 64, 60, 56, 41, 39, 35, 32, 30, 26, 23, 20, 17, 14, 11, 9 }

  51. 541236202396940482

    Returns: {85, 82, 78, 76, 73, 71, 65, 63, 60, 57, 50, 47, 45, 40, 27, 25, 23, 18, 16, 10, 5 }

  52. 223709553458541154

    Returns: {83, 81, 73, 71, 67, 64, 62, 60, 57, 54, 48, 46, 41, 39, 36, 33, 30, 26, 21, 19, 15, 12, 8, 3 }

  53. 623419452740446466

    Returns: {85, 83, 80, 75, 73, 67, 65, 63, 58, 53, 50, 47, 45, 38, 36, 34, 27, 23, 21, 19, 16, 13, 10, 4, 1 }

  54. 478266388726818946

    Returns: {85, 80, 78, 76, 68, 66, 64, 58, 54, 51, 41, 38, 36, 33, 30, 26, 22, 20, 15, 10, 6, 4 }

  55. 918109826091268098

    Returns: {86, 83, 81, 78, 73, 71, 68, 64, 58, 54, 52, 48, 45, 41, 39, 35, 25, 21, 17, 12, 10, 5, 4 }

  56. 1511

    Returns: {15, 13, 11 }

  57. 2808514547833530

    Returns: {74, 71, 69, 62, 59, 52, 50, 46, 43, 39, 36, 33, 30, 28, 26, 20, 16, 14, 12, 9, 7, 4, 1 }

  58. 2161024950

    Returns: {45, 41, 37, 35, 31, 28, 24, 20, 16, 10, 7, 2 }

  59. 56951

    Returns: {23, 19, 17, 15, 12, 5 }

  60. 45812384649114146

    Returns: {80, 76, 74, 69, 67, 64, 60, 58, 54, 49, 40, 38, 34, 32, 30, 24, 22, 18, 14, 11, 8, 5 }

  61. 130

    Returns: {10, 8, 2, 1 }

  62. 9201093028

    Returns: {48, 44, 41, 35, 32, 29, 26, 23, 17, 15, 11, 7, 5 }

  63. 48229265495165994

    Returns: {80, 77, 73, 67, 64, 57, 55, 53, 51, 48, 46, 43, 41, 36, 34, 31, 29, 25, 23, 21, 6, 4 }

  64. 648619080569258882

    Returns: {85, 83, 81, 76, 72, 69, 67, 64, 59, 54, 52, 50, 47, 41, 38, 36, 30, 28, 24, 21, 17, 5, 3 }

  65. 3820078895

    Returns: {46, 43, 39, 37, 33, 27, 20, 15, 10, 7, 6 }

  66. 6498091

    Returns: {33, 28, 26, 24, 19, 17, 11, 7, 4, 3 }

  67. 8572223706

    Returns: {48, 43, 38, 36, 32, 29, 26, 24, 22, 20, 15, 13, 9, 7, 2 }

  68. 5813653

    Returns: {33, 24, 22, 19, 12, 9, 7, 2 }

  69. 88256392

    Returns: {38, 36, 29, 21, 17, 12, 5, 4 }

  70. 12742492056

    Returns: {49, 39, 37, 34, 32, 30, 28, 25, 23, 21, 17, 10, 5 }

  71. 7977779787

    Returns: {48, 40, 36, 34, 23, 21, 19, 15, 13, 10, 4, 1 }

  72. 1110849

    Returns: {29, 26, 24, 19, 13, 11, 9, 6, 3 }

  73. 749898521971726

    Returns: {71, 69, 66, 63, 61, 58, 56, 53, 51, 45, 41, 35, 32, 29, 24, 20, 16, 13, 11, 6, 2, 1 }

  74. 53225231622692074

    Returns: {80, 78, 72, 66, 63, 59, 54, 52, 50, 45, 43, 38, 36, 34, 31, 29, 27, 25, 22, 15, 12, 5, 1 }

  75. 6

    Returns: {4 }

  76. 59102

    Returns: {23, 20, 16, 11, 8, 4, 1 }

  77. 247730839291

    Returns: {55, 50, 44, 41, 39, 34, 20, 18, 12, 8, 4, 3 }

  78. 37531279848

    Returns: {51, 46, 44, 42, 37, 29, 27, 25, 21, 19, 17, 13, 11, 9, 4 }

  79. 136763998154518

    Returns: {68, 64, 59, 56, 49, 44, 39, 35, 32, 30, 25, 22, 18, 16, 13, 10, 6, 3 }

  80. 6

    Returns: {4 }

  81. 12243115352138

    Returns: {63, 59, 52, 50, 48, 46, 42, 36, 33, 30, 28, 26, 23, 21, 17, 13, 5, 3 }

  82. 43028343855

    Returns: {51, 48, 45, 42, 36, 32, 29, 14, 12, 9, 7, 1 }

  83. 4

    Returns: {3 }

  84. 116793705923149

    Returns: {67, 65, 63, 61, 59, 52, 50, 47, 45, 43, 41, 39, 28, 25, 23, 19, 15, 10, 8, 1 }

  85. 1076281484914785

    Returns: {72, 69, 67, 62, 53, 47, 44, 41, 37, 34, 32, 29, 12, 9, 4 }

  86. 7445897173

    Returns: {47, 45, 43, 38, 36, 34, 32, 27, 25, 23, 19, 15, 12, 11 }

  87. 948053236827664

    Returns: {72, 68, 64, 62, 54, 46, 43, 40, 38, 36, 34, 32, 28, 24, 19, 16 }

  88. 440814102420487618

    Returns: {85, 78, 76, 71, 68, 59, 49, 46, 44, 40, 37, 35, 32, 28, 26, 24, 22, 20, 18, 14, 11, 8, 5, 4 }

  89. 191122

    Returns: {25, 23, 21, 18, 15, 13, 10, 5 }

  90. 44

    Returns: {8, 5 }

  91. 225399917128891

    Returns: {69, 65, 62, 57, 52, 50, 47, 45, 42, 35, 33, 23, 21, 16, 12, 6, 3, 2 }

  92. 61547245

    Returns: {37, 35, 33, 30, 27, 25, 22, 20, 14, 10, 8, 6, 2 }

  93. 84332979570467378

    Returns: {81, 78, 76, 74, 72, 67, 65, 62, 59, 55, 52, 50, 48, 41, 39, 29, 27, 22, 17, 13, 11, 9, 6, 3, 2 }

  94. 7

    Returns: {3, 2 }

  95. 81611965203379874

    Returns: {81, 78, 76, 69, 67, 65, 63, 61, 55, 53, 50, 48, 46, 43, 36, 33, 28, 23, 20, 18, 14, 11, 5, 4 }

  96. 12

    Returns: {5, 2 }

  97. 4

    Returns: {3 }

  98. 3348845

    Returns: {31, 29, 27, 21, 17, 13, 3, 2 }

  99. 13690449091698456

    Returns: {77, 75, 73, 64, 62, 57, 55, 53, 45, 40, 37, 31, 28, 25, 22, 20, 18, 15, 13, 8, 3, 2 }

  100. 14896962521413

    Returns: {63, 61, 55, 48, 41, 39, 34, 31, 29, 27, 25, 21, 19, 9, 7, 3, 2 }

  101. 19595478878

    Returns: {49, 47, 45, 41, 38, 36, 34, 28, 26, 24, 22, 20, 10, 7, 5, 1 }

  102. 5758985

    Returns: {33, 23, 19, 17, 12, 10, 8, 6, 3 }

  103. 147048402795308

    Returns: {68, 65, 59, 52, 39, 37, 35, 29, 23, 21, 17, 13, 11, 6, 4 }

  104. 4921274

    Returns: {32, 30, 23, 17, 15, 13, 10, 5, 4 }

  105. 62092

    Returns: {23, 20, 18, 13, 11, 9, 5, 4 }

  106. 1000000000000000000

    Returns: {86, 84, 80, 78, 76, 74, 70, 67, 65, 60, 58, 49, 47, 45, 43, 35, 31, 28, 25, 23, 20, 16, 14, 11, 8, 6, 2, 1 }

  107. 999999999999999999

    Returns: {86, 84, 80, 78, 76, 74, 70, 67, 65, 60, 58, 49, 47, 45, 43, 35, 31, 28, 25, 23, 20, 16, 14, 11, 8, 6, 3 }

  108. 679891637636434004

    Returns: {85, 83, 81, 79, 77, 75, 73, 71, 69, 67, 65, 63, 61, 59, 57, 55, 53, 51, 49, 47, 45, 43, 41, 39, 37, 35, 33, 30, 7, 2, 1 }

  109. 5

    Returns: {2, 1 }

  110. 10

    Returns: {4, 3 }

  111. 8

    Returns: {4, 1 }

  112. 260266999321390411

    Returns: {84, 71, 67, 55, 53, 49, 40, 38, 32, 28, 15, 13, 10, 3, 2 }

  113. 679891637638612260

    Returns: {85, 84 }

  114. 100000000000006183

    Returns: {82, 71, 69, 67, 65, 63, 61, 58, 54, 51, 47, 45, 40, 36, 34, 31, 28, 27 }

  115. 259695496911122587

    Returns: {83, 82 }

  116. 14

    Returns: {6 }

  117. 7778742051

    Returns: {47, 46 }

  118. 100

    Returns: {10, 4, 3 }

  119. 37889062373143908

    Returns: {79, 78 }

  120. 121394

    Returns: {25 }

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.
This problem was used for: