Statistics

Problem Statement for "CombiningSlimes"

Problem Statement

The idols Ami and Mami like playing games. Today they bought a new game. At the beginning of the game a group of slimes appears on the screen. In each turn of the game the player can select any two of the slimes and merge them together. The game ends when there is only one slime left.

Each slime has a positive integer size. Whenever the player merges two slimes, the size of the merged slime is x+y, where x and y are the sizes of the two merged slimes. Additionally, the player is awarded x*y mascots for performing this merge.

Ami and Mami have just started a new game. You are given a int[] a containing the initial sizes of all slimes. Ami and Mami really like mascots. Find and return the maximum total number of mascots they can obtain during the game.

Definition

Class:
CombiningSlimes
Method:
maxMascots
Parameters:
int[]
Returns:
int
Method signature:
int maxMascots(int[] a)
(be sure your method is public)

Constraints

  • a will contain between 2 and 100 elements, inclusive.
  • Each element of a will be between 1 and 100, inclusive.

Examples

  1. {3,4}

    Returns: 12

    There are two slimes, their sizes are 3 and 4. There is only one possible move: we merge them into a single slime of size 7. Doing so gives us 3*4 = 12 mascots.

  2. {2,2,2}

    Returns: 12

    In the first turn we will merge any two slimes. The size of the new slime will be 2+2 = 4, and we will gain 2*2 = 4 mascots. In the second turn we will merge the two remaining slimes. The size of the final slime will be 4+2 = 6. The second merge will give us 4*2 = 8 mascots. Hence, the total number of mascots we will obtain is 4 + 8 = 12.

  3. {1,2,3}

    Returns: 11

    One optimal solution looks as follows: First, merge slimes of sizes 1 and 3. This produces a slime of size 4, and we get 3 mascots. Then, merge slimes of sizes 4 and 2. This produces a slime of size 6, and we get 8 mascots.

  4. {3,1,2}

    Returns: 11

    The set of slimes is the same as in Example 2, therefore the correct answer is also the same. As we can merge any two slimes, their order in a does not matter.

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

    Returns: 395

  6. {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,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,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,100,100,100,100,100,100,100,100,100,100}

    Returns: 49500000

  7. {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,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,1,1}

    Returns: 4950

  8. {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,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100}

    Returns: 12582075

  9. {31,91,41,19,29,18,98,23,38,65,65,55,73,48,40,68,38,93,77,2,1,59,77,37,41,84,35,15,8,75,97,80,90,93,72,59,36,49,78,34,99,9,37,85,33,39,3,99,43,84,69,29,16,60,88,63,25,10,32,80,94,21,55,23,79,39,50,55,46,33,94,40,40,23,94,7,14,70,55,25,39,95,48,31,99,70,99,8,21,58,87,33,45,22,55,21,75,97,64,89}

    Returns: 13592399

  10. {96,30,62,27,10,24,81,79,69,44,45,28,33,15,70,31,13,61,50,13,63,53,59,16,25,15,86,64,94,80,68,54,73,93,47,61,29,71,72,95,42,61,70,41,82,10,91,51,43,1,29,74,60,90,76,8,23,91,18,97,23,43,88,6,26,37,91,94,60,36,13,52,96,82,40,88,77,95,99,53,65,55,72,3,95,82,94,24,15,10,5,88,27,22,42,77,26,7,23,4}

    Returns: 13299996

  11. {39,4,10,17,55,58,53,45,51,91,82,34,78,10,100,35,90,84,74,49,72,25,13,85,9,30,52,62,70,5,55,49,43,2,5,28,100,73,16,4,80,68,24,62,43,54,79,24,41,32,38,7,19,15,64,27,82,90,1,67,10,1,80,79,88,70,69,23,71,40,56,12,79,5,46,5,71,68,95,44,89,34,39,21,40,20,57,40,97,38,8,94,57,87,4,56,33,25,42,15}

    Returns: 10809266

  12. {95,30,15,7,69,94,30,2,71,59,46,20,10,51,69,53,74,45,40,98,79,23,91,84,43,53,21,37,11,30,27,48,57,75,16,7,13,72,25,67,2,31,14,99,23,82,13,1,85,21,12,2,64,100,65,17,61,49,34,93,94,93,94,6,68,39,31,21,16,54,16,74,21,49,61,83,21,75,89,34,98,40,19,100,23,9,10,40,27,55,98,18,93,98,78,40,97,11,16,72}

    Returns: 11385022

  13. {53,96,13,76,4,72,5,22,71,87,83,20,25,22,60,95,4,30,74,3,13,77,87,58,96,78,79,8,31,78,75,46,45,71,66,25,86,20,37,90,46,21,45,3,33,52,43,81,65,24,37,28,81,17,84,78,100,72,33,68,23,17,92,37,16,62,85,8,24,78,69,45,29,57,25,91,19,37,64,96,31,94,75,36,54,38,93,30,5,1,37,81,9,3,71,2,33,93,48,19}

    Returns: 11932917

  14. {69,89,29,32,9,88,70,31,98,86,100,5,9,57,69,91,74,33,97,22,18,96,21,79,20,72,96,13,100,5,66,84,26,57,88,50,14,85,27,40,15,62,41,92,73,39,57,52,45,85,98,42,92,33,82,97,77,56,99,94,67,13,47,36,94,82,76,53,15,28,78,38,66,61,28,57,75,14,84,89,92,78,43,37,83,32,85,9,55,12,96,61,87,45,67,43,26,29,65,75}

    Returns: 16421244

  15. {20,78,66,81,74,39,53,91,40,66,23,36,31,52,65,4,53,62,88,85,91,27,84,41,91,73,30,77,1,85,9,77,51,73,35,29,87,81,53,35,68,21,48,34,69,12,10,95,9,30,20,38,76,17,77,23,45,50,44,9,88,35,13,3,29,64,97,77,10,98,14,18,62,53,29,91,39,57,39,82,97,92,6,16,95,91,37,79,61,3,13,52,47,25,97,17,57,76,24,58}

    Returns: 12697444

  16. {3,66,10,53,71,82,72,19,61,48,64,21,2,17,5,2,20,88,74,65,88,41,41,55,61,29,97,34,73,83,92,41,85,86,23,79,50,2,47,33,13,3,14,55,83,80,72,50,82,40,50,61,18,15,64,64,39,51,34,28,89,36,10,95,33,53,91,47,24,55,21,87,66,40,63,49,9,5,65,50,1,8,40,30,82,21,50,35,76,85,38,21,62,95,12,99,47,95,61,32}

    Returns: 11734325

  17. {64,92,29,67,14,39,5,19,87,28,39,63,91,47,67,57,53,67,67,58,65,25,27,22,52,69,39,96,50,97,100,95,79,46,73,66,6,70,10,37,66,26,14,49,53,41,41,79,10,6,48,91,81,59,99,63,62,9,27,33,22,5,58,84,85,24,84,43,85,35,4,23,69,58,10,44,82,71,17,53,6,37,23,31,65,97,36,91,1,11,45,63,4,66,62,31,73,46,94,32}

    Returns: 12356240

  18. {48,62,57,88,25,93,79,83,27,39,31,90,36,68,26,78,9,21,65,12,52,16,95,6,92,13,28,92,8,77,31,31,86,41,59,30,6,10,5,4,31,84,7,53,69,88,83,100,64,31,65,12,8,11,11,18,5,48,16,38,93,27,27,46,12,26,45,27,87,33,4,17,24,67,45,25,12,60,60,37,38,61,66,68,64,92,92,94,52,30,2,30,41,50,42,83,29,28,99,84}

    Returns: 10340575

  19. {1,1}

    Returns: 1

  20. {1,100}

    Returns: 100

  21. {50,50}

    Returns: 2500

  22. {100,100}

    Returns: 10000

  23. {1,1,1,2,2,3,100}

    Returns: 1040

  24. {27,42,36,70,25,15,2,46,60,43,21,49,96,28,29,16,57,50,49,16,99,31,42,8,49,74,17,49,52,58,14,60,65,59,19,79,90,29,60,90,49,77,42,44,53,36,11,59,33,71,63,48,42,63,52,78,92,20,3,48,28,69,40,49,1,73,17,8,1,25,8,56,41,36,74,66,35,36,80,96,26,31,72,24,3,24,63,30,67,71,34,70,93,42,49,37,18,90,28,22}

    Returns: 10162935

  25. {62,68,32,97,30,84,82,41,94,88,30,97,64,65,65,78,50,83,99,30,49,51,50,67,47,30,21,92,4,34,32,29,24,69,93,39,18,19,96,43,47,91,46,5,20,86,99,8,14,23,74,35,85,51,29,80,83,73,85,100,21,39,51,63,66,39,12,54,39,20,90,62,60,16,59,70,97,67,61,44,18}

    Returns: 9652168

  26. {71,96,91,44,59,74,82,38,68,5,31,33,2,36,10,10,48,83,83,75,14,29,31,92,39,9,9,87,96,82,100,95,93,88,34,98,63,36,76,27,3,71,5,59,50,18,7,53,50,68,21,95,32,20,58,19,46,61,86,52,51}

    Returns: 4889311

  27. {26,30,4,52,92,35,6,31,29,70,13,55,98,12,31,23,73,74,61,76,41,10,77,56,3,33,97,66,7,16,19,74,98,30,58,83,60,61}

    Returns: 1526507

  28. {33,69,40,79,76,12,41,88,74,92,79,78}

    Returns: 261910

  29. {79,38,24,68,64,38,4,57,32,88,63,79,46,22,64,77,83,2,99,1,24,10,37,78,2,50,74,43,81,49,93,47,19,80,59,100,99,9,30,93,36,32,24,19,4,68,25,54,19,36,49,64,90,21,14,5,32,59,48,79,18,32,49,17,98,92,67,41,70,59,32,30,81,28,14,49,35,70,63,99,77,32,2,100,92,24,30,58,54,43,43,5,52,79,51,66,62}

    Returns: 11348651

  30. {82,90,36,36,25,52,6,11,84,1,35,29,62,55,49,73,25,100,88,65,94,36,32,100,98,62,96,80,26,35,44,22,76,91,53,24,46,36}

    Returns: 2040206

  31. {70,30,84,68,53,95,30,40,33,59,28,35,66,38,32,50,8,30,28,24}

    Returns: 380880

  32. {27,27,60,15,24,68,13,79,23,57,9,13,22,53,58,49,26,25,40,70,88,97,90,49,21,65,68,36,58,1,17}

    Returns: 868715

  33. {61,74,39,34,15,54,72,56,75,16,46,68,29,40,33,67,74,67,86,97,67,98,75,39,56,83,34,72,12,17,16,22,29,69,59,3,9,96,50,85,78,7,51,47,74,57,85,85,20,48,31,78,93,31,12,31,14,30,77,23,93,94,64,73,87,67,82,94,37,51,35,28}

    Returns: 7362181

  34. {88,76,54,7,61,38,24,63,53,45,97,69,9,52,27,92,79,39,83,47,26,64,66,50,52,19,3,7,54,79,86,100,47,58,40,96,51,16,40,32,29,78,93,8,91,82,25,10,61,45,66,58,20,94,3,22,33,93,45,5,17,34,95,90,62,11,46,10,39,7,89,74,84,33,24,94,77,20,98,43,4,40,37,81,61,89,97,65,49,82,86,80,64,85,62,76}

    Returns: 13108361

  35. {5,32,61,82,68,66,66,55,22,100,54,15,81,22,59,33,78,52,17,76,53,60,64,100,41,48,66,36,46,96,90,26,50,46,68,83,81,4,72,73,44,18,20,98,49,73,84,63,33,83,38,41,58,76,66,50,42,4,67,76,35,78,15,41,48}

    Returns: 6174055

  36. {92,87,35,36,11,30,49,30,33,29,72,67,31,74,28,21,23,41,36,28,1,88,9,81,59,12,30,22,31,50,42,37,64,84,83}

    Returns: 1149827

  37. {32,46,64,3,9,57,62,19,43,39,98,47,60,6,91,74,93,65,10,93,25,81,13,48,71,41,63,6,25,12,72,4,70,6,33,31,67,73,67,18,46,25,33,62,10,79,87,40,27,62,33,6,93}

    Returns: 2899559

  38. {94,46,95,92,21,87,58,18,85,90,54,85,20,20,72,17,31,88,96,32,64,48,9,77,24,19,75,86,78,73,28,23,87,38,86,85,75,24,84,27,40,40,99,56,66,35,59,69,30,21,38,48,79,77,64,34,66,11,64,5,97,2,38,29,99,90,81,91,69}

    Returns: 7497328

  39. {67,78,48,35,14,50,61,60,5,58,77,49,40,94,10,11,60,25,77,51,82,83,90,49,2,30,74,96,47,43,59,45,42,83,89,31,66,31}

    Returns: 1958384

  40. {26,94,91,42,3,61,17,5,92,84,70,54,77,43,81,5,61,9,25,19,93,37,67,85,53,85,71,74,16,44,19,17,95,85,16,70,89,49,62,96,85,5,70,87,63,44,18,7,72,86,15,8,84,62,58,71,97,18,13,49,82,96,35,7,37,10,62,66,9,82,96,63,42,91,68,42,86,48,74,42,64,70,54,12,79,60}

    Returns: 10744811

  41. {21,53,62,57,89,60,57,22,38,49,42,36,100,40,53,19,3}

    Returns: 297160

  42. {89,52,73,62,1,62,72,78,5,69,39,52,88,62,88,89,20,99,38}

    Returns: 606112

  43. {24,88,80,47,93,22,46,61,53,23,58,52,84,23,42,38,79,85,7,38,74,69,58,20,32,64,42,85,62,12,69,48,80,70,19,99,87,17,39,22,28,33,25,4,3,24,4,72,11,43,77,88,33,72,3,31,32,3}

    Returns: 3552023

  44. {2, 2, 2 }

    Returns: 12

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

    Returns: 7670

  46. {3, 4 }

    Returns: 12

  47. {10, 11, 12, 13 }

    Returns: 791

  48. {3, 1, 1 }

    Returns: 7

  49. {2, 5, 9, 10 }

    Returns: 233

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: