Statistics

Problem Statement for "DivideLoot"

Problem Statement

N pirates have stolen a treasure chest. The treasure chest contains some loot. The prices of the individual items in the chest are given in the int[] loot. There are at least N, but less than 2N items in the chest.

The pirates want to divide the loot according to the following rules:

  • Each pirate must get at least one item.
  • Each pirate must get at most two items.
  • Each pirate must get items with the same total price.

Return "possible" if the pirates can divide the loot according to the above rules, or "impossible" if they cannot do that.

Definition

Class:
DivideLoot
Method:
verify
Parameters:
int, int[]
Returns:
String
Method signature:
String verify(int N, int[] loot)
(be sure your method is public)

Notes

  • Note that the return value is case-sensitive.
  • Each item must be assigned to one of the pirates. It is not allowed to leave items without an owner.

Constraints

  • N will be between 1 and 50, inclusive.
  • loot will contain between N and 2N-1 elements, inclusive.
  • Each element of loot will be between 1 and 1000, inclusive.

Examples

  1. 1

    {47}

    Returns: "possible"

    The only pirate gets the only item.

  2. 3

    {10, 8, 10, 1, 1}

    Returns: "impossible"

    We cannot divide these items according to the rules. The only way in which each pirate gets the same total value requires one pirate getting three items (8+1+1) which is not allowed.

  3. 3

    {3, 9, 10, 7, 1}

    Returns: "possible"

    One pirate gets 3+7, one gets 9+1, and one gets 10.

  4. 6

    {1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1}

    Returns: "possible"

  5. 2

    {40, 1, 42}

    Returns: "impossible"

  6. 1

    {1}

    Returns: "possible"

  7. 2

    {1, 1}

    Returns: "possible"

  8. 2

    {1, 1, 1}

    Returns: "impossible"

  9. 4

    {1, 1, 1, 1}

    Returns: "possible"

  10. 3

    {1, 1, 1, 1}

    Returns: "impossible"

  11. 6

    {14, 24, 20, 4, 16, 8, 10, 18, 24, 6}

    Returns: "possible"

  12. 1

    {27}

    Returns: "possible"

  13. 12

    {4, 4, 1, 6, 1, 5, 6, 5, 5, 4, 5, 6, 3, 5, 3, 4, 6, 2, 6, 6}

    Returns: "impossible"

  14. 38

    {3, 12, 9, 5, 3, 7, 5, 5, 2, 7, 10, 6, 1, 8, 4, 5, 1, 5, 8, 2, 9, 9, 8, 5, 8, 8, 4, 5, 10, 11, 6, 8, 7, 8, 9, 2, 5, 12, 5, 3, 5, 2, 6, 8, 5, 10, 11, 8, 2, 13, 8, 5, 8, 11, 8, 7, 5, 1, 6, 11, 4, 6, 1, 8, 11, 7, 8, 5, 4, 12, 12, 3, 7, 6, 10}

    Returns: "possible"

  15. 1

    {3}

    Returns: "possible"

  16. 14

    {11, 10, 11, 1, 5, 6, 4, 9, 4, 6, 6, 3, 4, 8}

    Returns: "impossible"

  17. 8

    {14, 8, 5, 21, 7, 13, 16, 21, 21, 21, 21}

    Returns: "possible"

  18. 3

    {4, 2, 1, 3}

    Returns: "impossible"

  19. 15

    {108, 108, 112, 25, 112, 112, 89, 112, 4, 23, 38, 74, 4, 87, 112, 112, 112, 74, 112, 112, 38}

    Returns: "possible"

  20. 17

    {4, 4, 1, 6, 1, 5, 1, 3, 6, 3, 6, 6, 5, 2, 1, 3, 3, 2, 5, 1, 4}

    Returns: "impossible"

  21. 6

    {4, 45, 36, 77, 15, 75, 81, 27, 6, 66, 54}

    Returns: "possible"

  22. 6

    {3, 2, 1, 2, 3, 3, 3, 3, 2, 3, 1}

    Returns: "impossible"

  23. 17

    {14, 11, 10, 24, 24, 23, 18, 14, 2, 13, 24, 7, 24, 8, 22, 1, 16, 15, 18, 8, 12, 9, 10, 16, 17, 6, 24, 6, 12}

    Returns: "possible"

  24. 5

    {1, 1, 1, 1, 1, 1}

    Returns: "impossible"

  25. 1

    {1}

    Returns: "possible"

  26. 2

    {8, 8}

    Returns: "possible"

  27. 1

    {776}

    Returns: "possible"

  28. 2

    {3, 69, 72}

    Returns: "possible"

  29. 14

    {2, 1, 5, 3, 3, 4, 6, 3, 1, 3, 6, 6, 5, 3}

    Returns: "impossible"

  30. 26

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: "impossible"

  31. 8

    {1, 2, 2, 3, 1, 3, 3, 2, 2, 3, 1, 1}

    Returns: "possible"

  32. 1

    {1}

    Returns: "possible"

  33. 3

    {5, 7, 5, 4}

    Returns: "impossible"

  34. 31

    {5, 5, 1, 3, 1, 3, 5, 4, 4, 4, 2, 4, 2, 3, 5, 5, 2, 4, 3, 5, 5, 2, 5, 2, 3, 1, 1, 5, 5, 2, 2, 5, 1, 4, 5, 2, 5}

    Returns: "impossible"

  35. 1

    {4}

    Returns: "possible"

  36. 2

    {137, 137}

    Returns: "possible"

  37. 1

    {48}

    Returns: "possible"

  38. 3

    {1, 2, 1, 2}

    Returns: "possible"

  39. 6

    {1, 4, 5, 4, 6, 6, 3, 6}

    Returns: "impossible"

  40. 6

    {203, 203, 203, 203, 203, 203}

    Returns: "possible"

  41. 13

    {11, 49, 39, 49, 49, 4, 38, 45, 19, 4, 8, 49, 45, 41, 49, 49, 11, 10, 38, 30}

    Returns: "possible"

  42. 1

    {21}

    Returns: "possible"

  43. 2

    {3, 1}

    Returns: "impossible"

  44. 29

    {6, 1, 8, 5, 8, 6, 8, 7, 8, 4, 5, 8, 8, 8, 1, 8, 8, 6, 7, 5, 8, 7, 1, 8, 3, 5, 2, 6, 8, 2, 7, 8, 2, 1, 6, 2, 4, 3, 8, 3, 3, 8, 2}

    Returns: "possible"

  45. 1

    {2}

    Returns: "possible"

  46. 9

    {188, 117, 83, 156, 54, 91, 50, 161, 125, 86, 192, 242, 242, 81, 151, 159}

    Returns: "possible"

  47. 13

    {4, 5, 5, 2, 1, 4, 8, 4, 4, 7, 7, 6, 6}

    Returns: "impossible"

  48. 1

    {57}

    Returns: "possible"

  49. 2

    {1, 1}

    Returns: "possible"

  50. 6

    {8, 3, 10, 3, 8, 12, 1, 4, 9}

    Returns: "impossible"

  51. 7

    {241, 201, 241, 241, 241, 40, 178, 63, 241}

    Returns: "possible"

  52. 1

    {53}

    Returns: "possible"

  53. 3

    {29, 15, 23, 9, 38}

    Returns: "possible"

  54. 1

    {33}

    Returns: "possible"

  55. 12

    {1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1}

    Returns: "impossible"

  56. 30

    {14, 11, 40, 60, 16, 60, 60, 39, 60, 42, 60, 60, 45, 60, 60, 60, 60, 60, 8, 60, 60, 7, 60, 33, 21, 27, 53, 52, 60, 60, 20, 60, 37, 23, 49, 44, 18, 46, 60, 15, 60}

    Returns: "possible"

  57. 24

    {3, 5, 5, 4, 1, 10, 6, 8, 5, 1, 6, 8, 9, 11, 9, 4, 5, 2, 10, 8, 9, 10, 3, 2, 8, 1, 4, 10, 9, 6, 9, 11, 1, 6, 11, 7, 8, 2, 7, 5, 10, 2}

    Returns: "impossible"

  58. 29

    {8, 14, 7, 4, 10, 1, 10, 14, 11, 13, 5, 2, 4, 1, 7, 4, 4, 14, 4, 9, 9, 4, 11, 2, 2, 4, 2, 2, 6, 11, 13}

    Returns: "impossible"

  59. 1

    {9}

    Returns: "possible"

  60. 34

    {5, 4, 11, 3, 6, 5, 11, 9, 9, 6, 8, 3, 2, 1, 5, 11, 9, 5, 10, 2, 9, 4, 5, 2, 10, 2, 5, 8, 7, 4, 3, 11, 4, 3, 2, 1, 4, 10, 10, 11, 6, 4, 3, 6, 2, 3, 10, 7, 11, 6}

    Returns: "impossible"

  61. 21

    {6, 15, 15, 7, 3, 8, 1, 14, 8, 6, 7, 9, 13, 13, 10, 13, 1, 9, 10, 10, 7, 7, 14, 13, 15, 7, 1, 4, 5, 15, 2, 7, 12, 2, 11}

    Returns: "impossible"

  62. 16

    {1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2}

    Returns: "impossible"

  63. 24

    {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1}

    Returns: "possible"

  64. 14

    {6, 4, 6, 6, 6, 5, 7, 4, 7, 5, 7, 3, 5, 7, 7, 1}

    Returns: "impossible"

  65. 1

    {14}

    Returns: "possible"

  66. 6

    {1, 1, 3, 2, 2, 2}

    Returns: "impossible"

  67. 2

    {331, 233, 98}

    Returns: "possible"

  68. 13

    {1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 1, 1}

    Returns: "impossible"

  69. 49

    {11, 2, 4, 11, 9, 3, 11, 11, 11, 8, 1, 3, 11, 11, 11, 6, 11, 11, 4, 2, 4, 11, 11, 11, 5, 11, 11, 11, 1, 9, 6, 10, 7, 11, 9, 11, 11, 7, 11, 10, 11, 2, 8, 1, 4, 10, 11, 11, 1, 7, 11, 11, 11, 5, 11, 11, 11, 9, 1, 11, 11, 11, 10, 7, 10, 2}

    Returns: "possible"

  70. 9

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: "impossible"

  71. 28

    {4, 5, 2, 3, 5, 1, 1, 2, 5, 3, 5, 5, 5, 3, 6, 3, 5, 3, 4, 2, 4, 4, 4, 2, 6, 5, 5, 5, 1, 1, 2, 2, 4, 2, 6, 3, 2}

    Returns: "impossible"

  72. 4

    {2, 2, 1, 2, 1, 1}

    Returns: "impossible"

  73. 1

    {2}

    Returns: "possible"

  74. 25

    {4, 3, 1, 1, 4, 3, 3, 3, 6, 3, 5, 5, 6, 4, 4, 2, 3, 1, 2, 6, 2, 6, 3, 1, 1, 4, 6, 6, 2, 5, 5, 4, 4, 2, 6, 3, 1, 3, 4, 7, 1, 7, 5, 1, 7, 6, 4}

    Returns: "possible"

  75. 8

    {6, 5, 3, 1, 8, 4, 5, 7, 1, 1, 1, 2, 3, 2, 3}

    Returns: "impossible"

  76. 20

    {2, 7, 7, 7, 5, 1, 5, 6, 3, 5, 5, 7, 2, 4, 2, 7, 6, 7, 4, 7, 6, 7, 3, 1, 7, 7, 7, 2, 1}

    Returns: "possible"

  77. 26

    {14, 14, 2, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 12}

    Returns: "possible"

  78. 1

    {2}

    Returns: "possible"

  79. 3

    {17, 9, 17, 8}

    Returns: "possible"

  80. 18

    {3, 2, 6, 4, 7, 9, 9, 5, 7, 8, 1, 9, 9, 5, 5, 4, 2, 8, 9, 9, 4, 8, 1, 9, 9, 9, 1}

    Returns: "possible"

  81. 46

    {8, 7, 7, 1, 11, 3, 12, 12, 13, 13, 5, 2, 15, 4, 9, 12, 15, 14, 3, 15, 7, 1, 9, 4, 12, 4, 16, 1, 10, 10, 4, 3, 2, 3, 14, 4, 7, 16, 15, 4, 15, 7, 14, 1, 2, 3, 6, 11, 5, 12, 12, 7, 11, 8, 13, 11, 14, 3, 1, 15, 4, 11, 2, 8, 5, 16, 13, 12, 2, 10, 11, 16, 13, 12, 8, 14, 1, 11, 8, 12, 16, 1, 15}

    Returns: "impossible"

  82. 21

    {2, 2, 1, 2, 1, 2, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1}

    Returns: "possible"

  83. 4

    {174, 73, 247, 247, 247}

    Returns: "possible"

  84. 20

    {1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 2, 1}

    Returns: "possible"

  85. 1

    {1}

    Returns: "possible"

  86. 40

    {4, 11, 3, 16, 16, 5, 16, 15, 7, 7, 7, 16, 12, 6, 11, 3, 13, 8, 4, 4, 16, 10, 16, 5, 16, 16, 16, 16, 16, 16, 12, 9, 8, 16, 1, 4, 9, 16, 7, 16, 12, 13, 15, 16, 12, 9, 16, 10, 12, 4, 16, 16, 1, 6, 16, 9, 16, 16}

    Returns: "possible"

  87. 25

    {2, 1, 2, 1, 3, 3, 2, 1, 2, 1, 3, 2, 1, 3, 2, 2, 2, 1, 3, 2, 2, 3, 3, 2, 3, 1, 3, 3, 3, 3, 2}

    Returns: "impossible"

  88. 7

    {2, 2, 1, 2, 1, 1, 1, 2, 1, 2, 2, 1, 1}

    Returns: "impossible"

  89. 15

    {84, 37, 30, 82, 96, 21, 14, 95, 96, 96, 96, 27, 96, 1, 12, 68, 96, 69, 96, 59, 28, 75, 66}

    Returns: "possible"

  90. 8

    {11, 1, 8, 11, 7, 4, 6, 13, 2, 3, 7, 5, 6}

    Returns: "impossible"

  91. 16

    {5, 3, 4, 4, 5, 1, 4, 2, 4, 6, 1, 2, 2, 4, 5, 3, 3, 3, 6, 1, 2, 6, 6, 1, 1}

    Returns: "impossible"

  92. 30

    {13, 6, 10, 13, 5, 11, 8, 13, 3, 13, 10, 13, 3, 13, 7, 3, 13, 1, 5, 10, 13, 11, 13, 3, 7, 9, 13, 10, 12, 6, 7, 13, 1, 13, 10, 13, 12, 8, 2, 13, 3, 13, 4, 6, 2}

    Returns: "possible"

  93. 10

    {1, 1, 2, 2, 5, 1, 2, 4, 2, 3, 4, 4}

    Returns: "impossible"

  94. 9

    {54, 44, 47, 3, 54, 34, 20, 8, 51, 11, 10, 54, 46, 7, 43}

    Returns: "possible"

  95. 43

    {21, 80, 91, 11, 7, 25, 70, 29, 80, 53, 59, 13, 50, 38, 45, 21, 44, 85, 11, 1, 38, 32, 60, 91, 80, 15, 90, 31, 43, 11, 64, 11, 81, 12, 39, 84, 73, 19, 52, 78, 6, 8, 91, 91, 5, 29, 10, 85, 27, 70, 72, 62, 86, 66, 41, 79, 91, 62, 18, 82, 48, 18, 53, 91, 54, 73, 47, 9, 38, 80, 46, 83, 21, 14, 77, 53, 6, 37, 70, 76}

    Returns: "possible"

  96. 3

    {5, 3, 5, 5}

    Returns: "impossible"

  97. 12

    {27, 962, 935, 962, 962, 840, 342, 841, 122, 269, 309, 962, 121, 620, 13, 962, 949, 693, 653}

    Returns: "possible"

  98. 1

    {2}

    Returns: "possible"

  99. 3

    {2, 13, 7, 1}

    Returns: "impossible"

  100. 3

    {123, 179, 38, 141, 56}

    Returns: "possible"

  101. 3

    {17, 52, 30, 22, 35}

    Returns: "possible"

  102. 29

    {3, 5, 5, 5, 5, 2, 4, 5, 3, 3, 3, 3, 5, 1, 4, 3, 3, 5, 2, 1, 4, 3, 4, 5, 3, 5, 2, 5, 4, 2, 4, 2, 2, 2, 5, 5, 4, 4, 2, 1, 4, 3, 1, 3, 1, 4, 5, 5, 1, 2, 1, 3, 1}

    Returns: "impossible"

  103. 1

    {678}

    Returns: "possible"

  104. 6

    {1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: "impossible"

  105. 2

    {1, 4}

    Returns: "impossible"

  106. 3

    {4, 6, 6, 2}

    Returns: "possible"

  107. 11

    {2, 3, 1, 1, 4, 3, 1, 2, 3, 2, 1, 2, 2, 3, 1, 2, 3, 1, 1, 3, 1}

    Returns: "impossible"

  108. 3

    {1, 6, 4}

    Returns: "impossible"

  109. 18

    {31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 3, 29, 31, 31, 28, 2, 31, 31, 31, 31}

    Returns: "possible"

  110. 22

    {2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 1}

    Returns: "impossible"

  111. 3

    {10, 10, 9, 1 }

    Returns: "possible"

  112. 50

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 25 }

    Returns: "impossible"

  113. 3

    {4, 3, 2 }

    Returns: "impossible"

  114. 2

    {10, 10, 10 }

    Returns: "impossible"

  115. 3

    {1, 1, 1, 1 }

    Returns: "impossible"

  116. 4

    {1, 1, 1, 1, 2, 2 }

    Returns: "possible"

  117. 3

    {7, 10, 11, 14, 21 }

    Returns: "possible"

  118. 4

    {3, 3, 3, 3, 3 }

    Returns: "impossible"

  119. 2

    {1, 6, 3 }

    Returns: "impossible"

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: