Statistics

Problem Statement for "Jewelry"

Problem Statement

You have been given a list of jewelry items that must be split amongst two people: Frank and Bob. Frank likes very expensive jewelry. Bob doesn't care how expensive the jewelry is, as long as he gets a lot of jewelry. Based on these criteria you have devised the following policy:
  • 1) Each piece of jewelry given to Frank must be valued greater than or equal to each piece of jewelry given to Bob. In other words, Frank's least expensive piece of jewelry must be valued greater than or equal to Bob's most expensive piece of jewelry.
  • 2) The total value of the jewelry given to Frank must exactly equal the total value of the jewelry given to Bob.
  • 3) There can be pieces of jewelry given to neither Bob nor Frank.
  • 4) Frank and Bob must each get at least 1 piece of jewelry.
Given the value of each piece, you will determine the number of different ways you can allocate the jewelry to Bob and Frank following the above policy. For example: 
	values = {1,2,5,3,4,5}
Valid allocations are:
  Bob       		Frank
  1,2		         3
  1,3        		 4
  1,4		         5  (first 5)
  1,4         		 5  (second 5)
  2,3 		         5  (first 5)
  2,3         		 5  (second 5)
   5  (first 5)		 5  (second 5)
   5  (second 5)	 5  (first 5)
1,2,3,4       		5,5
Note that each '5' is a different piece of jewelry and needs to be accounted for separately. There are 9 legal ways of allocating the jewelry to Bob and Frank given the policy, so your method would return 9.

Definition

Class:
Jewelry
Method:
howMany
Parameters:
int[]
Returns:
long
Method signature:
long howMany(int[] values)
(be sure your method is public)

Constraints

  • values will contain between 2 and 30 elements inclusive.
  • Each element of values will be between 1 and 1000 inclusive.

Examples

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

    Returns: 9

    From above.

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

    Returns: 7

  3. {1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000}

    Returns: 18252025766940

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

    Returns: 4

    Valid allocations: Bob Frank 1,2 3 2,3 5 1,3 4 1,4 5

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

    Returns: 607

  6. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    Returns: 18252025766940

  7. {1,1,1,1,1}

    Returns: 50

  8. {100,100,100,100,100, 100,100,100,100,100, 100,100,100,100,100, 100,100,100,100,100, 100,100,100,100,100, 100,100,100,100,100}

    Returns: 18252025766940

  9. {1,2,3}

    Returns: 1

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

    Returns: 9

  11. {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}

    Returns: 25328912

  12. {1,2,3,5,7, 11,13,17,19,23, 29,31,37,41,43, 47,53,57,59,61, 63,65,67,69,71, 73,75,77,79,81}

    Returns: 8392289

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

    Returns: 313031087

  14. {3,10,30,28,26,27,29,20,7,6,11,6,18,29,26,17,30,3,23,7,20,2,19,21,15,6,3,1,31,18}

    Returns: 25309171

  15. {25,19,27,2,5,25,24,28,20,31,19,22,6,30,28,25,28,22,9,12,31,24,3,9,6,15,16,4,20,25}

    Returns: 37568712

  16. {25,22,24,29,9,16,27,28,21,29,21,24,31,7,19,13,26,8,24,26,25,6,31,10,3,1,31,20,18,14}

    Returns: 29259892

  17. {7,29,11,26,7,25,22,31,30,11,16,21,25,3,12,13,17,19,18,16,13,1,26,20,11,11,5,8,17,29}

    Returns: 27457415

  18. {9,29,13,13,30,30,13,28,3,3,20,20,11,24,23,11,7,16,15,26,16,30,6,30,21,19,24,22,18,30}

    Returns: 25625094

  19. {21,2,31,22,12,3,25,18,24,31,26,8,21,2,18,12,21,30,30,10,22,13,9,1,29,2,10,12,5,23}

    Returns: 27902921

  20. {16,10,18,30,9,1,5,5,22,3,15,14,31,29,10,12,15,24,26,2,6,17,27,21,9,6,14,18,8,7}

    Returns: 31118560

  21. {27,24,29,1,31,13,17,8,17,31,1,10,21,2,22,27,8,3,6,12,15,28,24,16,26,14,10,7,10,7}

    Returns: 27095989

  22. {14,9,15,21,7,23,30,21,25,6,23,30,4,18,26,8,27,24,27,14,18,29,30,2,13,2,25,14,12,22}

    Returns: 26653902

  23. {26,23,22,27,18,23,30,4,10,20,26,13,28,21,22,24,11,15,1,29,25,1,24,1,9,11,11,15,15,9}

    Returns: 28518447

  24. {26,27,5,1,6,27,31,27,24,27,30,5,17,4,9,13,23,22,10,18,21,13,20,20,21,21,17,17,11,5}

    Returns: 30978128

  25. {25,11,28,20,27,8,6,12,2,28,14,29,4,15,21,5,5,27,10,27,23,28,14,11,27,5,24,16,3,17}

    Returns: 28125308

  26. {31,28,19,12,7,25,21,13,7,20,10,10,19,9,23,4,15,5,15,2,2,9,24,10,3,15,9,25,5,25}

    Returns: 31974841

  27. {15,31,2,3,26,23,25,18,13,2,12,10,11,2,11,20,12,29,30,6,15,17,19,20,11,17,4,27,11,26}

    Returns: 29591577

  28. {3,30,2,22,11,20,24,16,1,15,4,8,25,25,31,25,4,18,8,7,9,10,21,28,10,23,5,23,7,7}

    Returns: 27454061

  29. {1,2,10,11,15,23,23,10,20,13,9,8,23,23,14,1,18,2,29,29,14,17,7,24,28,10,13,3,17,14}

    Returns: 39016554

  30. {15,28,25,2,31,4,21,17,6,18,11,7,13,6,22,19,8,9,24,7,28,10,18,10,5,4,30,23,4,27}

    Returns: 25822059

  31. {29,20,8,22,26,10,28,17,1,9,17,6,23,7,22,20,27,25,12,14,6,1,30,30,13,30,6,23,7,27}

    Returns: 26419614

  32. {8,2,16,3,27,16,19,24,18,13,26,20,30,19,20,5,29,25,28,9,24,16,22,1,23,28,2,3,14,18}

    Returns: 27488117

  33. {15,21,1,26,29,29,31,14,16,18,31,24,24,21,4,3,22,7,29,24,17,5,29,3,28,26,24,4,5,8}

    Returns: 36330945

  34. {22,6,11,6,31,8,19,20,2,6,31,6,14,26,2,29,14,15,31,14,4,23,17,6,30,15,13,22,1,15}

    Returns: 29226435

  35. {14,13,8,31,15,12,12,3,24,29,23,14,26,15,16,10,13,30,13,4,8,8,11,19,15,17,30,27,3,17}

    Returns: 33973515

  36. {19,3,17,10,2,21,12,8,15,2,12,12,4,29,14,13,15,24,19,30,16,24,2,8,5,25,1,23,16,18}

    Returns: 33134267

  37. {31,31,20,28,30,18,4,31,13,17,21,6,25,24,22,4,26,19,28,12,2,21,3,6,14,11,5,3,16,27}

    Returns: 23740565

  38. {13,1,26,26,16,19,16,10,30,25,26,6,7,15,27,6,29,31,16,19,12,29,22,15,22,21,25,1,18,5}

    Returns: 29566186

  39. {14,5,28,13,16,16,12,18,20,29,22,9,9,12,18,24,12,29,25,4,25,28,24,30,9,1,14,27,25,1}

    Returns: 30125530

  40. {10,27,22,20,24,4,2,8,25,14,13,4,30,13,19,24,31,31,17,29,28,28,10,18,12,11,20,21,27,31}

    Returns: 25504526

  41. {26,1,28,7,21,4,2,29,26,30,24,13,11,5,12,23,20,29,8,15,31,14,11,9,19,2,20,26,12,17}

    Returns: 27888009

  42. {26,6,15,25,1,10,20,13,23,26,24,26,27,12,28,17,5,11,13,29,19,19,22,25,17,10,14,4,27,5}

    Returns: 26165626

  43. {28,20,27,2,13,18,6,18,20,28,29,1,1,23,21,22,28,22,30,5,23,14,7,25,14,17,17,17,22,2}

    Returns: 33153611

  44. {89,141,213,349,371,408,634,696,699,738,886,910}

    Returns: 0

  45. {80,101,224,337,493,598,650,686,872,918,951,984}

    Returns: 0

  46. {4,200,276,291,428,505,525,579,852,916,965,992}

    Returns: 0

  47. {38,62,125,233,249,461,468,562,563,696,782,790}

    Returns: 0

  48. {9,16,41,110,265,405,465,475,648,847,877,944}

    Returns: 0

  49. {123,217,661,678,796,964,54,111,417,526,917,923}

    Returns: 0

  50. {26,107,203,264,437,486,542,627,736,833,860,916}

    Returns: 0

  51. {59,244,396,404,543,588,683,747,750,786,870,894}

    Returns: 0

  52. {6,27,375,392,427,468,529,616,691,877,941,993}

    Returns: 0

  53. {84,126,173,216,255,481,601,677,792,838,904,949}

    Returns: 0

  54. {51,56,96,245,274,472,658,784,806,809,822,962}

    Returns: 0

  55. {20,60,132,260,297,409,478,494,597,642,728,971}

    Returns: 0

  56. {39,167,228,329,470,532,666,736,786,855,912,976}

    Returns: 0

  57. {33,77,157,274,330,420,504,615,724,857,865,917}

    Returns: 0

  58. {27,130,146,231,310,414,552,632,716,785,857,968}

    Returns: 0

  59. {689,689,689,689,689,77,77,77,77,77,775,775,775,775,775,74,74,74,74,74,148,148,148,148,148,223,223,223,223,223}

    Returns: 656500

  60. {282,282,282,282,282,709,709,709,709,709,387,387,387,387,387,339,339,339,339,339,48,48,48,48,48,245,245,245,245,245}

    Returns: 5524376

  61. {502,502,502,502,502,546,546,546,546,546,819,819,819,819,819,139,139,139,139,139,675,675,675,675,675,306,306,306,306,306}

    Returns: 652725

  62. {675,675,675,675,675,740,740,740,740,740,50,50,50,50,50,518,518,518,518,518,922,922,922,922,922,534,534,534,534,534}

    Returns: 822550

  63. {569,569,569,569,569,434,434,434,434,434,324,324,324,324,324,669,669,669,669,669,929,929,929,929,929,257,257,257,257,257}

    Returns: 2162325

  64. {523,523,523,523,523,137,137,137,137,137,772,772,772,772,772,899,899,899,899,899,175,175,175,175,175,428,428,428,428,428}

    Returns: 1277550

  65. {805,805,805,805,805,919,919,919,919,919,92,92,92,92,92,348,348,348,348,348,787,787,787,787,787,93,93,93,93,93}

    Returns: 1269050

  66. {640,640,640,640,640,953,953,953,953,953,239,239,239,239,239,429,429,429,429,429,753,753,753,753,753,243,243,243,243,243}

    Returns: 5430300

  67. {277,277,277,277,277,692,692,692,692,692,184,184,184,184,184,325,325,325,325,325,189,189,189,189,189,661,661,661,661,661}

    Returns: 1581940

  68. {27,27,27,27,27,255,255,255,255,255,260,260,260,260,260,405,405,405,405,405,131,131,131,131,131,662,662,662,662,662}

    Returns: 5920080

  69. {857,857,857,857,857,848,848,848,848,848,741,741,741,741,741,563,563,563,563,563,979,979,979,979,979,770,770,770,770,770}

    Returns: 2462625

  70. {608,608,608,608,608,464,464,464,464,464,342,342,342,342,342,170,170,170,170,170,847,847,847,847,847,2,2,2,2,2}

    Returns: 3773800

  71. {509,509,509,509,509,611,611,611,611,611,5,5,5,5,5,843,843,843,843,843,797,797,797,797,797,786,786,786,786,786}

    Returns: 431050

  72. {195,195,195,195,195,535,535,535,535,535,449,449,449,449,449,10,10,10,10,10,619,619,619,619,619,311,311,311,311,311}

    Returns: 4505840

  73. {52,52,52,52,52,792,792,792,792,792,515,515,515,515,515,587,587,587,587,587,287,287,287,287,287,931,931,931,931,931}

    Returns: 3515950

  74. {1000,999,998,997,996,995,994,993,992,991,990,989,988,987,986,985,984,983,982,981 ,980,979,978,977,976,975,974,973,972,15}

    Returns: 1480

  75. { 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: 18252025766940

  76. { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 12, 13, 20, 30, 40, 40, 40, 40, 50 }

    Returns: 32868031

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: