Statistics

Problem Statement for "SevenSegmentDisplayNim"

Problem Statement

A seven-segment display is a cheap and easy way to show all possible digits and some small subset of letters. It looks as follows: 

   
   *---0---*
   |       |
   1       2
   |       |
   *---3---*
   |       |
   4       5
   |       |
   *---6---*

Note that in the figure we gave the segments numbers from 0 to 6.

Alice and Bob are playing a game of NIM on such a display. On each segment of the display there is a pile of pebbles of some size. The players take alternating turns. Each turn looks as follows:

  • The current player selects some collection of segments. The only restrictions are that the collection must be non-empty and acyclic. E.g., it is not allowed to select segments 0, 1, 3, 4, 5, 6 because four of them form a cycle.
  • The current player removes at least one pebble from each of the selected segments. There are no other restrictions on the numbers of pebbles removed from the individual segments (they do not have to be identical but they also do not have to be distinct).

Alice goes first. The player who is unable to perform a valid move loses.


You are given the int[]s LO and HI with 7 elements each.

Consider all starting positions such that for each i, the initial number of pebbles on segment i is between LO[i] and HI[i], inclusive. Among them, count all those from which Alice can win the game regardless of what Bob does. Return that count modulo 10^9 + 7.

Definition

Class:
SevenSegmentDisplayNim
Method:
whoWins
Parameters:
int[], int[]
Returns:
int
Method signature:
int whoWins(int[] LO, int[] HI)
(be sure your method is public)

Constraints

  • LO and HI will have exactly 7 elements each.
  • For each i, 0 <= LO[i] <= HI[i] <= 10,000.

Examples

  1. {10, 20, 0, 30, 0, 40, 40}

    {10, 20, 0, 30, 0, 40, 40}

    Returns: 1

    As LO=HI, we have just a single test case. In this test case there are some pebbles placed on the segments that form the digit 5: *---10--* | 20 | *---30--* | 40 | *---40--* The best first move for Alice (in fact, the only winning move) is to select exactly these five segments and to remove all pebbles from each of them.

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

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

    Returns: 0

    Again, we are looking at just a single starting configuration: six pebbles, each on a different segment. (These segments form the digit 0 on the display.) Alice cannot remove all pebbles in her turn. And regardless of what she removes, Bob will be able to remove the rest when it's his turn.

  3. {123, 789, 1213, 1617, 2021, 2425, 2829}

    {456, 1011, 1415, 1819, 2223, 2627, 3031}

    Returns: 317007411

    Remember to compute the answer modulo 10^9 + 7.

  4. {1, 1, 1, 1, 1, 1, 1}

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

    Returns: 1078

  5. {0, 0, 0, 0, 0, 0, 0}

    {10000, 0, 0, 0, 0, 10000, 0}

    Returns: 100020000

    If all piles start empty, Alice loses. Otherwise, Alice takes all pebbles and wins.

  6. {0, 0, 0, 0, 0, 0, 0}

    {10000, 10000, 10000, 10000, 10000, 10000, 10000}

    Returns: 915998171

  7. {0, 0, 0, 0, 0, 0, 0}

    {4, 5, 6, 6, 10, 6, 10}

    Returns: 1245059

  8. {360, 64, 440, 566, 464, 584, 351}

    {9263, 9524, 9395, 9401, 9630, 9041, 9814}

    Returns: 501370429

  9. {428, 674, 24, 980, 104, 0, 270}

    {9965, 9988, 9811, 9493, 9741, 9559, 9009}

    Returns: 933704060

  10. {939, 835, 920, 323, 581, 437, 235}

    {9243, 9535, 9526, 9367, 9452, 9980, 9247}

    Returns: 775600783

  11. {34, 574, 383, 733, 704, 361, 615}

    {9350, 9571, 9588, 9780, 9200, 9244, 9807}

    Returns: 938336236

  12. {860, 746, 936, 957, 36, 128, 341}

    {9100, 9371, 9592, 9392, 9520, 9553, 9832}

    Returns: 935745996

  13. {258, 99, 664, 892, 902, 232, 949}

    {9715, 9865, 9342, 9223, 9482, 9762, 9112}

    Returns: 499101870

  14. {791, 426, 619, 361, 691, 893, 293}

    {9900, 9791, 9829, 9244, 9828, 9568, 9944}

    Returns: 325772932

  15. {267, 365, 545, 578, 41, 495, 319}

    {9576, 9798, 9404, 9266, 9967, 9747, 9531}

    Returns: 73756733

  16. {818, 226, 620, 116, 642, 861, 212}

    {9388, 9497, 9259, 9985, 9618, 9947, 9571}

    Returns: 868619289

  17. {152, 454, 15, 174, 560, 642, 823}

    {9779, 9084, 9076, 9272, 9523, 9832, 9637}

    Returns: 59517170

  18. {559, 487, 801, 821, 446, 374, 940}

    {9777, 9033, 9622, 9271, 9920, 9659, 9623}

    Returns: 349518416

  19. {529, 966, 690, 931, 483, 936, 725}

    {9653, 9817, 9974, 9322, 9849, 9022, 9590}

    Returns: 797431759

  20. {248, 216, 354, 441, 981, 887, 708}

    {9188, 9180, 9481, 9943, 9203, 9130, 9100}

    Returns: 755517077

  21. {139, 747, 803, 583, 352, 540, 401}

    {9110, 9273, 9454, 9000, 9668, 9125, 9424}

    Returns: 926278497

  22. {68, 378, 21, 270, 42, 143, 185}

    {9756, 9523, 9855, 9502, 9205, 9801, 9791}

    Returns: 876331044

  23. {831, 506, 540, 464, 577, 580, 10}

    {9711, 9075, 9179, 9855, 9154, 9943, 9556}

    Returns: 615189437

  24. {346, 650, 887, 47, 898, 636, 240}

    {9729, 9062, 9387, 9126, 9022, 9090, 9309}

    Returns: 428653861

  25. {55, 900, 561, 315, 244, 627, 917}

    {9751, 9547, 9154, 9563, 9593, 9780, 9279}

    Returns: 448699096

  26. {633, 878, 584, 82, 576, 503, 350}

    {9569, 9053, 9976, 9117, 9423, 9427, 9362}

    Returns: 924897327

  27. {928, 310, 577, 864, 777, 500, 612}

    {9143, 9065, 9994, 9520, 9119, 9924, 9472}

    Returns: 274399056

  28. {0, 0, 0, 0, 0, 0, 0}

    {9773, 9251, 9360, 9815, 9339, 9170, 9473}

    Returns: 439729611

  29. {0, 0, 0, 0, 0, 0, 0}

    {9843, 9695, 9293, 9041, 9790, 9269, 9555}

    Returns: 525413386

  30. {0, 0, 0, 0, 0, 0, 0}

    {9421, 9788, 9699, 9917, 9919, 9209, 9749}

    Returns: 659369584

  31. {0, 0, 0, 0, 0, 0, 0}

    {9835, 9955, 9095, 9875, 9637, 9761, 9436}

    Returns: 729162278

  32. {0, 0, 0, 0, 0, 0, 0}

    {9215, 9296, 9214, 9476, 9871, 9677, 9840}

    Returns: 847852468

  33. {0, 0, 0, 0, 0, 0, 0}

    {9000, 9028, 9432, 9886, 9468, 9532, 9448}

    Returns: 345217108

  34. {0, 0, 0, 0, 0, 0, 0}

    {9344, 9509, 9436, 9978, 9240, 9515, 9583}

    Returns: 974190368

  35. {0, 0, 0, 0, 0, 0, 0}

    {9834, 9043, 9185, 9627, 9951, 9185, 9638}

    Returns: 575269202

  36. {0, 0, 0, 0, 0, 0, 0}

    {9952, 9612, 9407, 9004, 9639, 9142, 9761}

    Returns: 687894531

  37. {0, 0, 0, 0, 0, 0, 0}

    {9748, 9125, 9523, 9410, 9104, 9088, 9808}

    Returns: 63846318

  38. {0, 0, 0, 0, 0, 0, 0}

    {9771, 1536, 6480, 8594, 8285, 5365, 7088}

    Returns: 862978955

  39. {0, 0, 0, 0, 0, 0, 0}

    {1718, 4137, 7954, 1519, 5852, 488, 6465}

    Returns: 665163718

  40. {0, 0, 0, 0, 0, 0, 0}

    {4701, 2905, 8000, 3954, 6626, 7768, 116}

    Returns: 885768788

  41. {0, 0, 0, 0, 0, 0, 0}

    {9665, 1735, 3916, 3002, 1311, 2322, 8438}

    Returns: 601561100

  42. {0, 0, 0, 0, 0, 0, 0}

    {1996, 6794, 4832, 8999, 3598, 5684, 1477}

    Returns: 710392684

  43. {0, 0, 0, 0, 0, 0, 0}

    {5232, 7029, 8294, 8946, 9382, 5770, 8542}

    Returns: 382575958

  44. {0, 0, 0, 0, 0, 0, 0}

    {5349, 804, 9825, 7021, 1657, 7195, 9549}

    Returns: 570031188

  45. {0, 0, 0, 0, 0, 0, 0}

    {6698, 7681, 8487, 7783, 8462, 1959, 3760}

    Returns: 116958369

  46. {0, 0, 0, 0, 0, 0, 0}

    {1190, 770, 9907, 4894, 725, 104, 4198}

    Returns: 605769081

  47. {0, 0, 0, 0, 0, 0, 0}

    {7331, 566, 4942, 9874, 4909, 6911, 1816}

    Returns: 626768487

  48. {3, 3, 3, 2, 0, 0, 0}

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

    Returns: 52

  49. {1, 1, 1, 2, 0, 0, 0}

    {3, 3, 3, 3, 0, 0, 0}

    Returns: 52

  50. {1, 1, 1, 2, 0, 0, 0}

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

    Returns: 1453

  51. {2, 2, 2, 0, 2, 2, 2}

    {3, 3, 3, 0, 3, 3, 3}

    Returns: 62

  52. {0, 0, 0, 1, 3, 3, 3}

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

    Returns: 8

  53. {1, 1, 1, 0, 0, 0, 0}

    {2, 2, 2, 0, 2, 2, 2}

    Returns: 214

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

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

    Returns: 189

  55. {0, 0, 0, 2, 0, 0, 0}

    {3, 3, 3, 2, 0, 0, 0}

    Returns: 63

  56. {0, 0, 0, 0, 0, 0, 0}

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

    Returns: 52

  57. {0, 0, 0, 1, 0, 0, 0}

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

    Returns: 5175

  58. {6465, 6486, 6526, 6208, 4231, 4201, 4163}

    {8800, 8748, 8715, 8621, 8345, 8323, 8326}

    Returns: 562835622

  59. {4300, 4279, 4285, 3724, 1724, 1646, 1688}

    {7016, 6990, 7005, 6900, 6897, 6897, 6967}

    Returns: 473958459

  60. {6515, 6523, 6468, 5725, 8233, 8250, 8261}

    {9043, 9043, 9042, 7652, 9082, 9046, 9066}

    Returns: 154992790

  61. {1951, 1997, 1977, 2261, 6829, 6853, 6878}

    {7090, 7091, 7027, 7333, 7070, 7066, 7136}

    Returns: 922532122

  62. {2976, 2961, 2963, 5815, 1511, 1478, 1561}

    {7739, 7698, 7733, 6988, 2127, 2103, 2120}

    Returns: 970688039

  63. {7103, 7085, 7006, 4998, 5683, 5690, 5685}

    {8975, 8986, 8912, 6017, 8023, 8009, 8013}

    Returns: 468401974

  64. {8255, 8276, 8280, 3335, 4890, 4928, 4915}

    {8535, 8496, 8516, 6052, 8375, 8353, 8406}

    Returns: 589626125

  65. {7362, 7403, 7412, 8145, 4945, 4921, 4954}

    {7662, 7673, 7671, 8653, 5015, 5090, 5108}

    Returns: 180646832

  66. {3103, 3117, 3188, 2160, 1755, 1826, 1783}

    {5392, 5354, 5395, 4828, 4300, 4287, 4310}

    Returns: 824424021

  67. {1003, 956, 947, 3133, 2219, 2269, 2292}

    {2242, 2240, 2250, 3877, 6137, 6169, 6099}

    Returns: 477155792

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

    {3, 9, 4, 8, 5, 8, 2}

    Returns: 1792

  69. {2, 3, 8, 5, 3, 0, 2}

    {9, 8, 9, 8, 3, 5, 6}

    Returns: 11520

  70. {7, 2, 0, 5, 8, 1, 1}

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

    Returns: 1008

  71. {8, 3, 6, 1, 5, 1, 5}

    {9, 4, 9, 4, 8, 6, 8}

    Returns: 6144

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

    {4, 9, 9, 9, 4, 7, 2}

    Returns: 7200

  73. {2, 4, 1, 3, 0, 3, 3}

    {9, 5, 4, 4, 4, 9, 7}

    Returns: 22400

  74. {1, 0, 2, 1, 3, 3, 1}

    {7, 6, 9, 6, 4, 6, 3}

    Returns: 56445

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

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

    Returns: 1296

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

    {8, 9, 7, 5, 6, 9, 1}

    Returns: 43200

  77. {4, 3, 8, 4, 5, 3, 5}

    {7, 8, 8, 7, 6, 8, 9}

    Returns: 5760

  78. {3436, 2907, 3103, 481, 8348, 4268, 4828}

    {9345, 9364, 3920, 680, 9963, 9923, 9978}

    Returns: 695494707

  79. {3253, 9698, 5516, 2847, 5370, 2575, 1237}

    {5624, 9907, 9162, 8263, 6106, 3027, 8084}

    Returns: 72243631

  80. {576, 7373, 1539, 4431, 4624, 3555, 1236}

    {6404, 7605, 4821, 8066, 5468, 7003, 4184}

    Returns: 539167280

  81. {5301, 4783, 2639, 2988, 3772, 594, 7760}

    {6267, 7531, 3965, 5941, 5062, 3548, 9414}

    Returns: 155313466

  82. {403, 151, 4486, 6812, 3867, 866, 1355}

    {5825, 4659, 9058, 8676, 7440, 7442, 2132}

    Returns: 264312531

  83. {6592, 3066, 752, 7408, 1633, 434, 7345}

    {7262, 4061, 6581, 8719, 8583, 9140, 8921}

    Returns: 815013309

  84. {7954, 2641, 2597, 4515, 3172, 8078, 4501}

    {8854, 9648, 3905, 5218, 9130, 8333, 7533}

    Returns: 854924511

  85. {4184, 1909, 3618, 535, 2259, 1388, 5310}

    {5521, 8603, 4165, 3702, 4006, 7338, 8972}

    Returns: 258977765

  86. {3539, 1541, 2573, 4554, 2285, 1289, 914}

    {5300, 4263, 8495, 5912, 2697, 3018, 8341}

    Returns: 321815655

  87. {2941, 1682, 687, 3038, 1416, 1616, 3200}

    {9893, 9101, 4687, 5252, 7366, 4518, 4889}

    Returns: 739178493

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: