Statistics

Problem Statement for "AliceAndBobMedium"

Problem Statement

Alice and Bob are playing a game of NIM.

The rules of NIM are as follows: There are several piles of stones. The players take alternating turns. In each turn, the current player selects one non-empty pile of stones and removes some stones from the pile. (The player must remove at least one stone. They can remove as many stones as they want, possibly all of them, but just from a single pile.) The game ends when all stones have been removed. The player who removed the last stone wins the game. Equivalently, the first player who is unable to make a valid move loses the game.

The game of NIM has a very simple strategy based on binary representations of pile sizes. A position in the game of NIM is winning if the bitwise XOR of the sizes of all piles is non-zero, and losing if the bitwise XOR of the sizes of all piles is zero. It can be shown that:

  • If it is your turn and you are in a losing position, you will lose the game if your opponent plays optimally.
  • If it is your turn and you are in a winning position, you will win the game if you play optimally.

Both Alice and Bob play the game of NIM optimally. It is now Alice's turn. You are given a description of the current state of the game: the int[] a. Each element of a represents the number of stones on one of the piles. Consider all possible first moves Alice can make in the given situation. For how many of them will Alice eventually win the game? Find and return that number.

(Two moves are considered distinct if they produce a different new sequence of pile sizes. In other words, we can distinguish between different piles that have the same number of stones. See Example #1.)

Definition

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

Constraints

  • a will contain between 1 and 37 elements, inclusive.
  • Each element of a will be between 1 and 737,373,737, inclusive.

Examples

  1. {737}

    Returns: 1

    There is a single pile with 737 stones. In this situation Alice has exactly one winning move: she should remove all stones and win immediately. If she does anything else, Bob will remove all the remaining stones and win.

  2. {7,3,7}

    Returns: 3

    In this situation Alice has three different winning moves: Remove three stones from the first pile. Remove three stones from the second pile. Remove three stones from the third pile.

  3. {3,7,3,7}

    Returns: 0

    Regardless of how Alice plays from this position, Bob will eventually win the game.

  4. {737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737}

    Returns: 0

  5. {737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737,737373737}

    Returns: 37

  6. {181119233,98802491,314160780,582670708,308278121,203553285,123970458,311274075,12979920,88309200,376622402,309015858,224972344,680725905,206822984,150933582,678105569,411586056,65089972,209907606,646584826,522877179,676131383,523618772,381040811,262948111,385445798,418967828,513245841,425421265,635493768,449677064,466985979,490361884,328612125,582352376,48275123}

    Returns: 7

  7. {18}

    Returns: 1

  8. {18,18}

    Returns: 0

  9. {1,3}

    Returns: 1

  10. {1,3,2}

    Returns: 0

  11. {12,10,10}

    Returns: 3

  12. {12,10,10,12}

    Returns: 0

  13. {30,10,12,8}

    Returns: 1

  14. {30,10,12,8,16}

    Returns: 0

  15. {4,20,3,3,28}

    Returns: 1

  16. {4,20,3,3,28,12}

    Returns: 0

  17. {22,22,13,26,13,22}

    Returns: 3

  18. {22,22,13,26,13,22,12}

    Returns: 0

  19. {28,14,30,24,30,11,28}

    Returns: 5

  20. {28,14,30,24,30,11,28,29}

    Returns: 0

  21. {28,29,7,22,26,4,30,30}

    Returns: 5

  22. {28,29,7,22,26,4,30,30,14}

    Returns: 0

  23. {25,22,11,8,20,8,12,10,20}

    Returns: 3

  24. {25,22,11,8,20,8,12,10,20,2}

    Returns: 0

  25. {22,24,12,7,18,14,15,8,22,19}

    Returns: 5

  26. {22,24,12,7,18,14,15,8,22,19,27}

    Returns: 0

  27. {386531516,419520249,291433391,160716850,227204367,474329175,84346086,58932297,327165220,239698894,257559988,243320916,441675325,103488617,395921577,11347515,477831003,198521128,396861878,413484939,394412880,225963873,253562775,146214775,145341109,457758171,530180524}

    Returns: 13

  28. {386531516,419520249,291433391,160716850,227204367,474329175,84346086,58932297,327165220,239698894,257559988,243320916,441675325,103488617,395921577,11347515,477831003,198521128,396861878,413484939,394412880,225963873,253562775,146214775,145341109,457758171,530180524,526263742}

    Returns: 0

  29. {338044897,460714533,524589236,152969400,111222219,529306965,120642294,324637987,86330996,182434957,410108244,89894132,473187352,16593592,211773367,9222226,293889980,416716563,520511362,458774711,223108110,485814204,527736110,104182124,351536328,39831983,495870433,183110424}

    Returns: 15

  30. {338044897,460714533,524589236,152969400,111222219,529306965,120642294,324637987,86330996,182434957,410108244,89894132,473187352,16593592,211773367,9222226,293889980,416716563,520511362,458774711,223108110,485814204,527736110,104182124,351536328,39831983,495870433,183110424,310203243}

    Returns: 0

  31. {5181651,395405883,35060996,465890536,118037691,456529277,390912712,127128195,348023802,117874192,173644735,417247983,392304241,291437902,55211885,287340329,261146188,280068180,69978269,450419968,22672933,455166594,507047075,407963699,386628790,521477647,87916671,44909403,427735663}

    Returns: 17

  32. {5181651,395405883,35060996,465890536,118037691,456529277,390912712,127128195,348023802,117874192,173644735,417247983,392304241,291437902,55211885,287340329,261146188,280068180,69978269,450419968,22672933,455166594,507047075,407963699,386628790,521477647,87916671,44909403,427735663,481709320}

    Returns: 0

  33. {439987483,79024985,315477907,225742524,387317581,113597118,98700925,330174406,314255249,105906860,439463024,486022279,101957615,172077710,521315200,360569644,198371318,189146960,202779080,67003183,193189904,155848613,150930191,13502947,475795621,218340859,35833813,252858756,343150330,354068673}

    Returns: 15

  34. {439987483,79024985,315477907,225742524,387317581,113597118,98700925,330174406,314255249,105906860,439463024,486022279,101957615,172077710,521315200,360569644,198371318,189146960,202779080,67003183,193189904,155848613,150930191,13502947,475795621,218340859,35833813,252858756,343150330,354068673,171151630}

    Returns: 0

  35. {415857347,427806872,472175523,444716930,358566685,286317431,353474017,282680458,127359811,443556433,90969832,206147424,135054572,188087642,505911239,250365192,374023570,445901398,535510425,219757751,503343628,270671767,489070242,179306544,122038190,98890050,129204002,169180771,300062184,504447513,123486529}

    Returns: 15

  36. {415857347,427806872,472175523,444716930,358566685,286317431,353474017,282680458,127359811,443556433,90969832,206147424,135054572,188087642,505911239,250365192,374023570,445901398,535510425,219757751,503343628,270671767,489070242,179306544,122038190,98890050,129204002,169180771,300062184,504447513,123486529,26318950}

    Returns: 0

  37. {454755718,195516090,455678518,426076698,172029000,23670555,341719534,527616288,267893824,495754720,124135022,412769422,403969980,121143499,313901764,222495438,164925401,480084803,314373160,36693295,354664437,406367290,319975005,473459936,134573285,394035790,435559331,32011799,520139671,477387080,505909294,163479755}

    Returns: 21

  38. {454755718,195516090,455678518,426076698,172029000,23670555,341719534,527616288,267893824,495754720,124135022,412769422,403969980,121143499,313901764,222495438,164925401,480084803,314373160,36693295,354664437,406367290,319975005,473459936,134573285,394035790,435559331,32011799,520139671,477387080,505909294,163479755,197751162}

    Returns: 0

  39. {118184728,446676992,87211493,33893593,174679045,386842568,466812583,388547803,200819822,16814031,478809760,162149737,258544558,389616806,485748573,275860620,296932111,246141548,446658613,45631094,85621711,34454092,39460283,477356786,442075255,467070177,109135216,98723563,44964936,472157599,107883668,62346697,433546589}

    Returns: 15

  40. {118184728,446676992,87211493,33893593,174679045,386842568,466812583,388547803,200819822,16814031,478809760,162149737,258544558,389616806,485748573,275860620,296932111,246141548,446658613,45631094,85621711,34454092,39460283,477356786,442075255,467070177,109135216,98723563,44964936,472157599,107883668,62346697,433546589,509375508}

    Returns: 0

  41. {269685749,78328130,5677351,427268525,195460397,372754323,339467166,452012101,367401500,345887097,133993888,131080835,180286161,3395223,59792418,293581130,94712384,306785072,322031270,430125666,504012492,306416660,85509640,263654445,350128560,106185455,287562864,502963426,225540035,372893228,534773974,152672593,292216885,165153652}

    Returns: 19

  42. {269685749,78328130,5677351,427268525,195460397,372754323,339467166,452012101,367401500,345887097,133993888,131080835,180286161,3395223,59792418,293581130,94712384,306785072,322031270,430125666,504012492,306416660,85509640,263654445,350128560,106185455,287562864,502963426,225540035,372893228,534773974,152672593,292216885,165153652,390048669}

    Returns: 0

  43. {462746239,27622509,60651687,416784795,223752419,258944842,444865374,22029522,199922162,288634849,180217303,182602736,36962775,384326406,278059663,350215901,35766863,165670858,402959783,455716728,265063438,4247600,347472928,287328481,187834412,345951142,414682576,351866377,196535104,110244961,150779726,4442265,94252889,222333884,345037964}

    Returns: 15

  44. {462746239,27622509,60651687,416784795,223752419,258944842,444865374,22029522,199922162,288634849,180217303,182602736,36962775,384326406,278059663,350215901,35766863,165670858,402959783,455716728,265063438,4247600,347472928,287328481,187834412,345951142,414682576,351866377,196535104,110244961,150779726,4442265,94252889,222333884,345037964,444114645}

    Returns: 0

  45. {335783007,94992912,113990092,512413109,42303453,140088325,232596956,65748348,391994557,242434626,171206817,288596613,178550876,286877994,230580616,250324948,118977558,496896802,113487386,194651680,487797170,146190724,494465945,97155841,374229979,279125985,322844120,459677899,171337020,196880332,514298336,528731183,101442424,468428264,202155012,455469133}

    Returns: 21

  46. {335783007,94992912,113990092,512413109,42303453,140088325,232596956,65748348,391994557,242434626,171206817,288596613,178550876,286877994,230580616,250324948,118977558,496896802,113487386,194651680,487797170,146190724,494465945,97155841,374229979,279125985,322844120,459677899,171337020,196880332,514298336,528731183,101442424,468428264,202155012,455469133,164958672}

    Returns: 0

  47. {332336617,431872447,447338181,275376266,458299329,420005478,455953865,452832054,313535021,473364220,289475713,314964348,328469853,480392796,346258609,411317699,449012530,449123379,498071284,316279432,305117383,303813153,408698867,332582072,335456588,468847645,465160968,514269801,274957426,297490043,443493303,297856035,456569168,487200730,303368984,324936818,526969650}

    Returns: 37

  48. {173875455,352951788,524678860,345703961,445767443,351174544,297650880,368310512,517820138,396031455,360323687,456362271,457962706,448965464,366130725,313915826,360597282,485727523,301283492,279775209,328966388,453446928,356845932,480398146,407845107,493307762,310811111,528991031,291173424,286672627,304446235,414797298,371975855,363621878,507453359,367805364}

    Returns: 35

  49. {470191008,425306565,505206435,510979909,505460176,465331905,523852326,288148988,506153730,527918920,310434672,299052411,332786321,398760744,301572076,525191326,381934967,286243253,504788291,411011611,465187670,354167790,374934763,449485711,435840868,392385178,395011332,499693902,415218898,330022953,347144699,439315094,305006182,451421141,353859221}

    Returns: 35

  50. {21807022,290476009,369553358,386699361,313066565,408349487,515957081,456411660,272835927,508210231,485877814,343606762,284936168,478575298,384871829,390670243,509737034,394736459,374338959,450173995,434864103,288760884,410599270,426151186,317907699,515803547,491373364,282800025,334869967,425737614,419228062,526526911,390015911,322432750}

    Returns: 33

  51. {501610290,471618499,286116271,288421956,351659093,320006241,456567259,376476029,347212753,480286698,380350777,417533902,447825685,533195311,377827126,445242236,508724546,348957246,489335881,354445475,316589947,317914266,529951393,458605840,438109229,358471132,496726737,420259734,509356693,444917804,414230857,305902869,536606705}

    Returns: 33

  52. {10, 6 }

    Returns: 1

  53. {1, 2, 3 }

    Returns: 0

  54. {13, 11, 1, 4 }

    Returns: 1

  55. {737373737, 737373737, 737373737, 737373737, 737373737 }

    Returns: 5

  56. {2323, 545, 454, 423244, 123, 34356, 5467, 8879, 7676, 4347 }

    Returns: 1

  57. {2 }

    Returns: 1

  58. {2, 1 }

    Returns: 1

  59. {4, 2 }

    Returns: 1

  60. {8, 8, 3 }

    Returns: 1

  61. {1, 8 }

    Returns: 1

  62. {7, 1, 6 }

    Returns: 0

  63. {8, 8, 8, 11 }

    Returns: 1

  64. {4, 13, 5 }

    Returns: 1

  65. {10, 10, 10 }

    Returns: 3

  66. {4, 4, 7 }

    Returns: 3

  67. {1, 2, 3, 4 }

    Returns: 1

  68. {6, 4 }

    Returns: 1

  69. {1, 2, 1 }

    Returns: 1

  70. {114716626, 282281698, 163619214, 474152762 }

    Returns: 1

  71. {1, 1, 1, 2 }

    Returns: 1

  72. {283507927, 88587648, 335562053, 143913276 }

    Returns: 1

  73. {6, 7, 15, 15 }

    Returns: 3

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: