Statistics

Problem Statement for "EllysFiveFriends"

Problem Statement

During the girl sleepovers, Elly and her friends happen to play games that involve the consumption of fluids. For the purpose of this problem, we will assume that the fluids consumed are apple juice and orange juice. (This does not necessarily correspond to reality.)

One of these games is the following: Five girls sit down in a circle. We will label the girls 0 through 4 in the order in which they sit. Note that the girls 0 and 4 sit next to each other. At the beginning of the game, each girl i picks a positive integer numbers[i] between one and ten thousand.
The game then proceeds in rounds. Each round involves two girls that sit next to each other. Both girls must have positive integers at the beginning of the round. There are two possible actions they may perform:

  • If both their integers are odd, they may perform the "apple action": they subtract 1 from each of their integers, and they share a glass of apple juice.
  • They may always perform the "orange action": They divide both their integers by 2 (rounding down, if the result is not an integer) and share a glass of orange juice.
The girls win the game if all of their numbers reach zero.

Elly once observed five of her friends playing this game. Elly recorded the game on a piece of paper: For each round, she wrote down the pair of girls that played in that round and the drink they chose. (The order in which she wrote down the two girls does not matter.) If the girls won the game, Elly gives the paper to you, otherwise she throws it away.

You are given the int[] numbers containing the integers the girls selected at the beginning of the game. Let X be the count of different ways in which the girls could have won the game. In other words, X is the number of different papers Elly could have written down and given to you. Your method must return this value modulo 1,000,000,007.

Definition

Class:
EllysFiveFriends
Method:
getZero
Parameters:
int[]
Returns:
int
Method signature:
int getZero(int[] numbers)
(be sure your method is public)

Constraints

  • numbers will contain exactly 5 elements.
  • Each element of numbers will be between 1 and 10000, inclusive.

Examples

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

    Returns: 10

    One of the ways in which the girls can win the game: Girls 0 and 1 drink orange juice. New integers: {2, 0, 1, 2, 3}. Girls 2 and 3 drink orange juice. New integers: {2, 0, 0, 1, 3}. Girls 3 and 4 drink apple juice. New integers: {2, 0, 0, 0, 2}. Girls 0 and 4 drink orange juice. New integers: {1, 0, 0, 0, 1}. Girls 0 and 4 drink apple juice. New integers: {0, 0, 0, 0, 0}. A different way of winning the game has the same first four steps, and then in step 5 girls 0 and 4 drink orange juice. Note that in step 2 girls 2 and 3 are not allowed to choose apple juice, as at that time at least one of their integers is even.

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

    Returns: 0

    Here the girls cannot win the game at all.

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

    Returns: 520

    Even with small numbers the answer can be rather big.

  4. {42, 666, 1337, 666, 42}

    Returns: 549119981

    Don't forget to use modular arithmetics.

  5. {8792, 9483, 6787, 9856, 6205}

    Returns: 165501353

    An almost maximal test case.

  6. {10000, 10000, 10000, 10000, 10000}

    Returns: 952019520

    The maximal test case.

  7. {8191, 7679, 8191, 8191, 8191}

    Returns: 96943536

  8. {8191, 8191, 8190, 8191, 7903}

    Returns: 728000940

  9. {4095, 4051, 4093, 3519, 4095}

    Returns: 608507667

  10. {4095, 3583, 4091, 4089, 3451}

    Returns: 967786370

  11. {8191, 8175, 8127, 8063, 8191}

    Returns: 656575715

  12. {4095, 4030, 3966, 4095, 4095}

    Returns: 203058268

  13. {7931, 8187, 8191, 8159, 8190}

    Returns: 146106497

  14. {8191, 8191, 8125, 7639, 8191}

    Returns: 102760698

  15. {8063, 8191, 8190, 7926, 8127}

    Returns: 789018504

  16. {108, 73, 59, 83, 15}

    Returns: 649244340

  17. {2092, 1860, 349, 381, 2832}

    Returns: 214615257

  18. {9798, 5127, 894, 9128, 2768}

    Returns: 841058825

  19. {7017, 9818, 5683, 7207, 5955}

    Returns: 734167753

  20. {3555, 7714, 8357, 4439, 6793}

    Returns: 661903612

  21. {2742, 9821, 5049, 4371, 7495}

    Returns: 930810925

  22. {5193, 3443, 9795, 1486, 6250}

    Returns: 897813839

  23. {8225, 8529, 9834, 7786, 2187}

    Returns: 49502806

  24. {7154, 2957, 6225, 7991, 7749}

    Returns: 562815297

  25. {9859, 4629, 6549, 6531, 3651}

    Returns: 624046546

  26. {5031, 5547, 8707, 3780, 5537}

    Returns: 400625703

  27. {8469, 7405, 8163, 3853, 8068}

    Returns: 395506601

  28. {169, 7018, 7084, 5327, 6545}

    Returns: 652313592

  29. {3237, 6061, 5507, 3920, 6217}

    Returns: 19971835

  30. {951, 7851, 6321, 3415, 5313}

    Returns: 837691353

  31. {2010, 7520, 8833, 8354, 8905}

    Returns: 754040984

  32. {8418, 581, 8344, 9486, 3132}

    Returns: 822154940

  33. {8886, 5191, 8213, 9, 9}

    Returns: 0

  34. {7492, 1995, 5732, 271, 8858}

    Returns: 414992505

  35. {7897, 5671, 8649, 7023, 2827}

    Returns: 231179251

  36. {8518, 2535, 7415, 3457, 1859}

    Returns: 81672842

  37. {1606, 3053, 1536, 7570, 6008}

    Returns: 185784779

  38. {2404, 10, 5038, 8, 9149}

    Returns: 0

  39. {1820, 4433, 8884, 2422, 255}

    Returns: 554759739

  40. {1, 9644, 3922, 2609, 6}

    Returns: 0

  41. {2498, 5732, 1690, 1011, 3803}

    Returns: 968924112

  42. {1190, 4946, 7461, 3925, 5134}

    Returns: 440641162

  43. {3086, 7583, 2192, 659, 7749}

    Returns: 24615103

  44. {5992, 5881, 3034, 3337, 694}

    Returns: 804218287

  45. {1860, 1174, 6724, 1740, 1025}

    Returns: 512590207

  46. {6358, 7358, 1843, 8781, 786}

    Returns: 430596598

  47. {5, 9, 4498, 1556, 6491}

    Returns: 0

  48. {5809, 822, 760, 1940, 6813}

    Returns: 454768944

  49. {7220, 2446, 3582, 9058, 4376}

    Returns: 911310851

  50. {8752, 6566, 4935, 1528, 4392}

    Returns: 336988534

  51. {3297, 7726, 5967, 4193, 3369}

    Returns: 820360365

  52. {737, 735, 2664, 895, 9904}

    Returns: 316801226

  53. {2499, 9093, 4383, 2180, 8155}

    Returns: 988350005

  54. {1772, 7305, 244, 9025, 8269}

    Returns: 158795462

  55. {2040, 381, 5423, 8998, 8028}

    Returns: 337693647

  56. {1435, 363, 7812, 1296, 5402}

    Returns: 27382320

  57. {2770, 5406, 186, 4, 9}

    Returns: 80528650

  58. {1217, 4084, 71, 2089, 2317}

    Returns: 243838394

  59. {1522, 1322, 8203, 3098, 9947}

    Returns: 911633880

  60. {1578, 8867, 8, 9524, 3}

    Returns: 0

  61. {5342, 2, 2230, 12, 2296}

    Returns: 0

  62. {1488, 3662, 7781, 620, 3687}

    Returns: 656070496

  63. {16, 2705, 2543, 7268, 10}

    Returns: 0

  64. {306, 9234, 4440, 278, 4200}

    Returns: 367286490

  65. {1556, 5902, 4732, 8048, 987}

    Returns: 721180580

  66. {5720, 9439, 13, 8038, 15}

    Returns: 0

  67. {10, 3358, 6786, 11, 2554}

    Returns: 0

  68. {7303, 1338, 5, 3434, 16}

    Returns: 0

  69. {3444, 9798, 1407, 7624, 8142}

    Returns: 785574275

  70. {9011, 7522, 3843, 8726, 72}

    Returns: 857393969

  71. {1, 1, 1, 1, 1}

    Returns: 0

  72. {10000, 10000, 10000, 10000, 10000 }

    Returns: 952019520

  73. {9878, 8786, 1234, 7685, 1233 }

    Returns: 532330050

  74. {133, 153, 117, 113, 107 }

    Returns: 72658195

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: