Statistics

Problem Statement for "DiceGames"

Problem Statement

You are attempting to create a new game that is played by rolling several dice. In order to determine scoring, you need to first know how many different formations can be rolled with those dice. We define a formation as the collection of values that are shown on the dice, without regard to order. Thus, {1, 1, 2}, {1, 2, 1}, and {2, 1, 1} are all the same formation, whereas {1, 1, 2}, {1, 2, 2} and {1, 1, 3} are all different formations. Note that even though two dice may have a different number of sides, for the purpose of counting formations, only the number shown on them matters.

You are given a int[] sides, where the i-th element is the number of sides on the i-th die. The sides of an n-sided die contain all numbers between 1 and n, inclusive. Return the number of different formations that can be made from those dice.

Definition

Class:
DiceGames
Method:
countFormations
Parameters:
int[]
Returns:
long
Method signature:
long countFormations(int[] sides)
(be sure your method is public)

Constraints

  • sides will contain between 1 and 32 elements, inclusive.
  • Each element of sides will be between 1 and 32, inclusive.

Examples

  1. {4}

    Returns: 4

    A single die with four sides can have four formations.

  2. {2, 2}

    Returns: 3

    This is essentially the equivalent of flipping two coins. We can get Heads/Heads, Heads/Tails, or Tails/Tails.

  3. {4, 4}

    Returns: 10

    Here, there are 10 formations we can make: {1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}, {2, 3}, {2, 4}, {3, 3}, {3, 4}, {4, 4}.

  4. {3, 4}

    Returns: 9

    Now it is impossible to get {4, 4} because the first die has only 3 sides.

  5. {4, 5, 6}

    Returns: 48

  6. {6, 5, 4}

    Returns: 48

  7. {32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32}

    Returns: 916312070471295267

  8. {32, 31, 30, 1, 2, 3, 4, 5, 29, 28, 27, 26, 25, 24, 6, 7, 8, 9, 10, 23, 22, 21, 20, 19, 18, 11, 12, 13, 14, 17, 16, 15}

    Returns: 55534064877048198

  9. {31, 4, 15, 9, 26, 5, 3, 5, 8, 9, 7, 9, 32, 3, 8, 4, 6, 24, 6, 3, 7, 5, 10, 5, 8, 20, 9, 7, 4, 9, 4, 4}

    Returns: 5340998296357

  10. {27, 18, 28, 18, 28, 4, 5, 9}

    Returns: 6505450

  11. {21,26,27,6,25,25,26,4,3,29,31,14,2,21,26,3,11,24,31,5,5,11,31,9,9,16,20,13,4,20,17,15}

    Returns: 40751200482175153

  12. {10,25,18,28,28,11,4,9,18,9,7,9,27,31,1,9,24,32,7,3,4,14,13,25,29,22,31,18,24,17,5,22}

    Returns: 56241707454859975

  13. {11,23,21,3,31,5,1,15,20,22,23,25,31,27,13,28,2,17,16,13,14,8,14,21,3,10,11,9,6,21,30,23}

    Returns: 25058975389115621

  14. {2,20,17,7,24,8,30,18,19,10,12,28,13,25,6,26,11,32,2,10,16,25,15,15,18,13,11,24,17,12,11,5}

    Returns: 23880236226918650

  15. {16,24,11,26,2,32,4,3,20,1,30,30,10,19,11,23,27,28,16,15,23,25,15,21,3,22,30,8,21,32,10,16}

    Returns: 83960541529664380

  16. {2,11,15,18,5,30,7,8,20,21,32,16,27,9,31,8,32,7,20,13,29,7,20,25,24,9,32,7,31,15,14,6}

    Returns: 118352445101142250

  17. {2,7,12,10,24,31,2,4,3,28,29,11,13,10,13,13,13,18,21,12,24,1,3,16,29,12,29,27,4,25,7,7}

    Returns: 4290229977279313

  18. {20,28,14,9,16,32,17,16,6,27,31,1,19,13,25,25,11,18,1,11,19,29,17,15,2,21,11,25,27,32,26,21}

    Returns: 68984484038903530

  19. {13,8,23,16,23,26,9,29,28,2,18,9,11,29,13,28,24,17,4,23,19,9,4,10,9,1,29,16,11,30,13,3}

    Returns: 14596617661458100

  20. {26,19,8,31,17,14,32,20,30,6,24,30,18,17,21,3,5,4,14,5,22,9,19,28,28,26,28,11,17,7,14,26}

    Returns: 174124851683269891

  21. {24,14,1,22,14,17,14,2,24,19,24,23,1,16,2,23,22,31,11,4,22,26,3,27,27,12,22,5,27,32,32,29}

    Returns: 32709129622677603

  22. {32,30,24,11,19,14,29,10,18,20,29,16,30,26,8,14,22,14,31,1,24,25,9,30,21,13,4,31,31,1,15,12}

    Returns: 116476145183960405

  23. {17,19,15,19,19,28,18,4,3,6,5,18,2,14,14,19,2,13,23,16,30,13,16,5,20,29,3,10,26,19,18,27}

    Returns: 5971454593209424

  24. {10,22,14,21,15,5,3,28,28,2,30,26,26,9,19,5,30,4,8,4,8,30,10,28,19,6,16,20,22,3,19,9}

    Returns: 15815400588156614

  25. {6,11,16,32,6,9,28,15,5,18,1,11,11,18,7,11,16,21,28,6,24,16,4,31,29,19,28,17,28,15,28,13}

    Returns: 44123209168172692

  26. {32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

    Returns: 55534064877048198

  27. {32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32 }

    Returns: 916312070471295267

  28. {32, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32 }

    Returns: 916312070471295266

  29. {6, 5, 4 }

    Returns: 48

  30. {23, 12, 32, 22, 32, 23, 1, 1, 2, 30, 30, 31, 31, 29, 29, 29, 29, 29, 29, 29, 30, 24, 25, 27, 27, 27, 23, 23, 1, 2 }

    Returns: 10379574199019698

  31. {10, 1, 10 }

    Returns: 55

  32. {4, 3 }

    Returns: 9

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

    Returns: 90

  34. {4 }

    Returns: 4

  35. {10, 1 }

    Returns: 10

  36. {5, 1 }

    Returns: 5

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

    Returns: 16796

  38. {31, 14, 19, 8, 1, 32, 12, 31, 32, 1, 1, 1, 5, 11, 9, 10, 20, 22, 30, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 9, 1 }

    Returns: 78763054287067

  39. {32, 32 }

    Returns: 528

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

    Returns: 14544636039226909

  41. {29, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32 }

    Returns: 916312070471294677

  42. {32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14, 14, 15, 15, 16, 16, 16, 17, 25 }

    Returns: 85343292199085256

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

    Returns: 55534064877048198

  44. {4, 2 }

    Returns: 7

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: