Statistics

Problem Statement for "RowAndManyCoins"

Problem Statement

Alice and Bob play the following game. The game board consists of some cells in a row. Each cell is marked either 'A' or 'B'. At the beginning, there are no coins placed on the board – all the cells are empty. Alice and Bob take alternating turns. Alice plays first. In each turn, the current player chooses some contiguous empty cells and places a coin onto each of the chosen cells. The player must always choose at least one cell. The player must never choose all empty cells. In other words, after each turn there must be at least one empty cell.

The following picture shows two examples of placing coins:


The game ends when there is only one cell left without a coin. If that cell is marked 'A', Alice wins. Otherwise, Bob wins. You are given a String cells representing the row of cells. Assuming that both players aim to win and play optimally, return a String containing the name of the winner.

Definition

Class:
RowAndManyCoins
Method:
getWinner
Parameters:
String
Returns:
String
Method signature:
String getWinner(String cells)
(be sure your method is public)

Constraints

  • cells will contain between 2 and 50 characters, inclusive.
  • Each character in cells will be either 'A' or 'B'.

Examples

  1. "ABBB"

    Returns: "Alice"

    Alice can win by placing coins on three cells marked 'B' in her first turn.

  2. "BBBB"

    Returns: "Bob"

  3. "BA"

    Returns: "Alice"

  4. "BABBABBB"

    Returns: "Bob"

  5. "ABABBBABAABBAA"

    Returns: "Alice"

  6. "BBBAAABBAAABBB"

    Returns: "Bob"

  7. "AA"

    Returns: "Alice"

  8. "BA"

    Returns: "Alice"

  9. "AB"

    Returns: "Alice"

  10. "BB"

    Returns: "Bob"

  11. "AAA"

    Returns: "Alice"

  12. "BAA"

    Returns: "Alice"

  13. "ABA"

    Returns: "Alice"

  14. "BBA"

    Returns: "Alice"

  15. "AAB"

    Returns: "Alice"

  16. "BAB"

    Returns: "Bob"

  17. "ABB"

    Returns: "Alice"

  18. "BBB"

    Returns: "Bob"

  19. "AAAA"

    Returns: "Alice"

  20. "BAAA"

    Returns: "Alice"

  21. "ABAA"

    Returns: "Alice"

  22. "BBAA"

    Returns: "Alice"

  23. "AABA"

    Returns: "Alice"

  24. "BABA"

    Returns: "Alice"

  25. "ABBA"

    Returns: "Alice"

  26. "BBBA"

    Returns: "Alice"

  27. "AAAB"

    Returns: "Alice"

  28. "BAAB"

    Returns: "Bob"

  29. "ABAB"

    Returns: "Alice"

  30. "BBAB"

    Returns: "Bob"

  31. "AABB"

    Returns: "Alice"

  32. "BABB"

    Returns: "Bob"

  33. "ABBB"

    Returns: "Alice"

  34. "BBBB"

    Returns: "Bob"

  35. "ABBAAABBBBABBABAAAAABBBA"

    Returns: "Alice"

  36. "ABBAAABBBBABBABAAAAABBBB"

    Returns: "Alice"

  37. "BBBAAABBBBABBABAAAAABBBA"

    Returns: "Alice"

  38. "BBBAAABBBBABBABAAAAABBBB"

    Returns: "Bob"

  39. "AAABAAABABBABBBBBAABBABABAABABBBBAAAAA"

    Returns: "Alice"

  40. "AAABAAABABBABBBBBAABBABABAABABBBBAAAAB"

    Returns: "Alice"

  41. "BAABAAABABBABBBBBAABBABABAABABBBBAAAAA"

    Returns: "Alice"

  42. "BAABAAABABBABBBBBAABBABABAABABBBBAAAAB"

    Returns: "Bob"

  43. "AAAABBBAAAAAABBBBBAA"

    Returns: "Alice"

  44. "AAAABBBAAAAAABBBBBAB"

    Returns: "Alice"

  45. "BAAABBBAAAAAABBBBBAA"

    Returns: "Alice"

  46. "BAAABBBAAAAAABBBBBAB"

    Returns: "Bob"

  47. "ABAABABABABBBAABA"

    Returns: "Alice"

  48. "ABAABABABABBBAABB"

    Returns: "Alice"

  49. "BBAABABABABBBAABA"

    Returns: "Alice"

  50. "BBAABABABABBBAABB"

    Returns: "Bob"

  51. "AABBBBBABBABBABABAABBAABBABAAA"

    Returns: "Alice"

  52. "AABBBBBABBABBABABAABBAABBABAAB"

    Returns: "Alice"

  53. "BABBBBBABBABBABABAABBAABBABAAA"

    Returns: "Alice"

  54. "BABBBBBABBABBABABAABBAABBABAAB"

    Returns: "Bob"

  55. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "Alice"

  56. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "Alice"

  57. "BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "Alice"

  58. "BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "Bob"

  59. "ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA"

    Returns: "Alice"

  60. "ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: "Alice"

  61. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA"

    Returns: "Alice"

  62. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: "Bob"

  63. "ABABABABABABABABABABABABABABABABABABABABABABABABA"

    Returns: "Alice"

  64. "ABABABABABABABABABABABABABABABABABABABABABABABABB"

    Returns: "Alice"

  65. "BBABABABABABABABABABABABABABABABABABABABABABABABA"

    Returns: "Alice"

  66. "BBABABABABABABABABABABABABABABABABABABABABABABABB"

    Returns: "Bob"

  67. "AABABABABABABABABABABABABABABABABABABABABABABABAA"

    Returns: "Alice"

  68. "AABABABABABABABABABABABABABABABABABABABABABABABAB"

    Returns: "Alice"

  69. "BABABABABABABABABABABABABABABABABABABABABABABABAA"

    Returns: "Alice"

  70. "BABABABABABABABABABABABABABABABABABABABABABABABAB"

    Returns: "Bob"

  71. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "Alice"

  72. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "Alice"

  73. "BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "Alice"

  74. "BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "Bob"

  75. "AAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "Alice"

  76. "AAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "Alice"

  77. "BAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "Alice"

  78. "BAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "Bob"

  79. "ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA"

    Returns: "Alice"

  80. "ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: "Alice"

  81. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA"

    Returns: "Alice"

  82. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: "Bob"

  83. "ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABA"

    Returns: "Alice"

  84. "ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABB"

    Returns: "Alice"

  85. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABA"

    Returns: "Alice"

  86. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABB"

    Returns: "Bob"

  87. "ABABABABABABABABABABABABABABABABABABABABABABABABAA"

    Returns: "Alice"

  88. "ABABABABABABABABABABABABABABABABABABABABABABABABAB"

    Returns: "Alice"

  89. "BBABABABABABABABABABABABABABABABABABABABABABABABAA"

    Returns: "Alice"

  90. "BBABABABABABABABABABABABABABABABABABABABABABABABAB"

    Returns: "Bob"

  91. "AABABABABABABABABABABABABABABABABABABABABABABABABA"

    Returns: "Alice"

  92. "AABABABABABABABABABABABABABABABABABABABABABABABABB"

    Returns: "Alice"

  93. "BABABABABABABABABABABABABABABABABABABABABABABABABA"

    Returns: "Alice"

  94. "BABABABABABABABABABABABABABABABABABABABABABABABABB"

    Returns: "Bob"

  95. "BBBABABBBBBBBA"

    Returns: "Alice"

  96. "BABAB"

    Returns: "Bob"

  97. "BBBBBABA"

    Returns: "Alice"

  98. "BABABABA"

    Returns: "Alice"

  99. "ABBBBA"

    Returns: "Alice"

  100. "BAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "Alice"

  101. "BABABAB"

    Returns: "Bob"

  102. "BAABAAB"

    Returns: "Bob"

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: