Statistics

Problem Statement for "RemoveGame"

Problem Statement

Fox Ciel and Toastman are playing the following game.


Initially, they are given a String. Each character of the String is either 'o' or 'x'. The first character of the String is always 'o' and the last character is always 'x'. 'o' characters are Ciel's characters, and 'x' characters are Toastman's characters.


The game is played as follows. Players take alternate turns, and Ciel makes the first turn. In each turn, the player must remove one of the opponent's characters. There must be at least one of the current player's characters to the left of the removed character, and one of the current player's characters to the right of the removed character.

For example, if the current state of the game is "oooxxoox" and it's Ciel's turn, she can remove either of the two 'x' characters in the middle, but she cannot remove the last 'x' character.


The game ends when a player cannot make a valid move. Once the game is over, each player counts the number of his/her characters that are still present in the String (i.e., characters that were not removed by the opponent during the game). The player with more characters wins. If both players have the same amount of characters, then it's a draw.

Both players use an optimal strategy. If a player can win, he/she will follow the strategy that guarantees that he/she wins and has the maximum number of characters at the end of the game. Otherwise, if a player can force the game to end in a draw, he/she will follow the strategy that does so. Otherwise, he/she will follow the strategy that minimizes the number of characters that the opponent has at the end of the game.


You are given a String field and an int R. The first character in field is 'o', the last character is 'x' and each of the other characters can be 'o', 'x' or '?'. You can obtain different initial placements of characters by replacing each '?' character in field with 'o' or 'x'.

Return the number of possible placements where Ciel wins and has at least R 'o' characters left at the end of the game.

Definition

Class:
RemoveGame
Method:
countWinning
Parameters:
String, int
Returns:
long
Method signature:
long countWinning(String field, int R)
(be sure your method is public)

Constraints

  • field will contain between 2 and 40 characters, inclusive.
  • Each character in field will be lowercase 'o', lowercase 'x' or '?'.
  • The first character in field will be 'o'.
  • The last character in field will be 'x'.
  • R will be between 1 and 40, inclusive.

Examples

  1. "o??x"

    2

    Returns: 2

    In this case, possible arrangements are as follows: ooox : Ciel wins with 3 'o' characters. ooxx : Ciel draws with Toastman. oxox : Ciel wins with 2 'o' characters. oxxx : Toastman wins with 3 'x' characters Thus, the number of arrangements where Ciel wins with at least 2 'o' characters is 2.

  2. "o??x"

    3

    Returns: 1

    In this case, only "ooox" is possible.

  3. "oxxxxoooox"

    2

    Returns: 1

    The game ends in "oox" and Ciel wins with 2 'o' characters.

  4. "ooooxxoxxx"

    1

    Returns: 0

    The game ends in "ooooxxxx" and Ciel draws with Toastman.

  5. "ox?o?ox"

    3

    Returns: 3

  6. "o????xooxooxxxxxxx"

    5

    Returns: 1

  7. "oxxxxxxxxxoooxooxoooooooooooo??????x"

    5

    Returns: 64

  8. "oo???xx???xx???oxox???xx"

    7

    Returns: 126

  9. "o??????????????????????????????????????x"

    1

    Returns: 143548512057

  10. "o??????????????????????????????????????x"

    8

    Returns: 82797734692

  11. "o??????????????????????????????????????x"

    15

    Returns: 9217086029

  12. "o??????????????????????????????????????x"

    22

    Returns: 292726058

  13. "o??????????????????????????????????????x"

    29

    Returns: 1169618

  14. "o??????????????????????????????????????x"

    36

    Returns: 778

  15. "o??????????????????????????????????????x"

    40

    Returns: 0

  16. "ox"

    1

    Returns: 0

  17. "ox"

    2

    Returns: 0

  18. "ox"

    3

    Returns: 0

  19. "ox"

    40

    Returns: 0

  20. "o???????????????xxx"

    1

    Returns: 9949

  21. "oooo????????xxxxxxxxx"

    1

    Returns: 9

  22. "oooooooo???????????????????xx"

    8

    Returns: 480492

  23. "oooo???????????xxxxxxxxx"

    6

    Returns: 226

  24. "o?????xxxx"

    1

    Returns: 5

  25. "oooo?????????xxxxxxx"

    8

    Returns: 124

  26. "o???????xxxxxxx"

    3

    Returns: 1

  27. "oooo????????????xxxx"

    2

    Returns: 2223

  28. "ox????o?xx"

    1

    Returns: 16

  29. "o???xx?x?x"

    2

    Returns: 2

  30. "ox???oo??x"

    3

    Returns: 22

  31. "oo?xx??oxx"

    4

    Returns: 1

  32. "o????x???x"

    5

    Returns: 15

  33. "o?x??xo?xoo?x?o??ox?x???x"

    2

    Returns: 1586

  34. "oxo?x??x?ox????oxx????xox"

    4

    Returns: 600

  35. "o?????xxx?????xx?o?oo??xx"

    6

    Returns: 1792

  36. "o??x???o???x?????o?x?xoox"

    8

    Returns: 3430

  37. "o???xo?x???xx??o?oxx?x??x"

    10

    Returns: 8

  38. "o??o?????oxo?oxo??x??oox?x?o?o?oo?????ox"

    3

    Returns: 1898712

  39. "oo?x?xox??x??x???x??o??xo?ox?oo?xx???o?x"

    7

    Returns: 122641

  40. "o??????oo???x?????xx??x????xoo???o???x?x"

    10

    Returns: 16108054

  41. "o?oo?xx????o?????xo?oxxo??o???o?????x??x"

    1

    Returns: 11369898

  42. "o??x???o?o?????o??o????oxo??o?oxoox??o?x"

    5

    Returns: 7337313

  43. "o???xx?????????o?o???xx???oox??o???oo??x"

    11

    Returns: 8098755

  44. "ox??o?oxo??xox?o?x??x????ox??o??x?o????x"

    12

    Returns: 140955

  45. "o??????ooxo???oxo???xo?xo?xx?ooo?x?????x"

    12

    Returns: 304350

  46. "o???ox??????xo??x??????x?o?????ox?????xx"

    6

    Returns: 71950129

  47. "oo???x??oxxxo?xo???ox?o???xox???o???ox?x"

    2

    Returns: 499978

  48. "o??????????x??xxo??x????oo?x?????oo???ox"

    5

    Returns: 57226005

  49. "ox???x?o??x???oxxoo???o??o???x?x?xo?x?ox"

    3

    Returns: 695860

  50. "o?ox???xo?o?ox?x??x?o?x?xox?x?o??xo??x?x"

    3

    Returns: 126008

  51. "o?x??ox??ox?xx??oo??o????x?ooooo?x?x???x"

    6

    Returns: 587879

  52. "oo????o??x???x???x??x???xxx??o??x?x??xxx"

    13

    Returns: 30716

  53. "o?x?x??xoo?oo???o???xoo????xo?x?o?o?oo?x"

    5

    Returns: 872205

  54. "oo???x????????x??o???o??ox??o??xo??oxo?x"

    8

    Returns: 13207306

  55. "oxxxxo?x???????o?o??x?????o?xx????oo?o?x"

    12

    Returns: 149172

  56. "oxooooooooxoooooooooooooxooxoxooooooooox"

    30

    Returns: 1

  57. "ooooxooooxoxooooooooooxooooooooooxooooox"

    31

    Returns: 0

  58. "ooxxxxooxxooxxxxoxoxoxoxxxxoxooxxoxoxoox"

    1

    Returns: 0

  59. "oxxxxoxoxoxoxxooooxoxxxoxxxxoxxxooxoxoox"

    1

    Returns: 0

  60. "ooxxxxxoxoxxxxxxxxxxxoxooxxxxxxxxxxxxxxx"

    1

    Returns: 0

  61. "ooxxxxooxxxxxxxxxoxoxxxxxoxxxxxxxxxxxxxx"

    1

    Returns: 0

  62. "oooooooooxoxooxoooooooxxoooxoxoxxoxoooox"

    20

    Returns: 1

  63. "ooooooooxoxoooxxoooooxxoxxxooooooooooxox"

    21

    Returns: 0

  64. "oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    1

    Returns: 0

  65. "oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    1

    Returns: 0

  66. "oxooxoooooxxxoxoxxoxxxxxxxooxxoxxoxoxoox"

    1

    Returns: 0

  67. "oxxxxxxoxoooooooxoooxxxooxoxxxooxoxxxxxx"

    1

    Returns: 0

  68. "o?????x??????o???????o?????????x???????x"

    29

    Returns: 13230

  69. "o?????o????????????x?o???????????x?????x"

    34

    Returns: 36

  70. "o?????????????xo?????????o?????x???????x"

    22

    Returns: 9494953

  71. "o???????????????x???o?????o????x???????x"

    28

    Returns: 60537

  72. "o????o???????????x?x??o????????????????x"

    26

    Returns: 384168

  73. "o??o?????????????????????x??ox?????????x"

    29

    Returns: 13160

  74. "o??????x?????x??o????????????????o?????x"

    32

    Returns: 631

  75. "o?????????????????????x???xo???o???????x"

    20

    Returns: 31529068

  76. "o???????????o????????o???x??????x??????x"

    20

    Returns: 38007688

  77. "o???????x?????????????????o?x?o????????x"

    28

    Returns: 59536

  78. "ox??????o?o????????????????x???????????x"

    21

    Returns: 14360746

  79. "o???????????o??x????????????ox?????????x"

    25

    Returns: 662424

  80. "oxx?xox???x???xxx??xx?xx?ox???xx?xxxx?ox"

    4

    Returns: 0

  81. "oo??o?oo?o?o?xo?xooo?ooooo?ox??o?oo????x"

    4

    Returns: 65536

  82. "oo??x?oxo?x?xx?x?xxxxxxx??xxx?x???x?x??x"

    5

    Returns: 0

  83. "o????ooo??xo??o?oo??o?oxo?o?o?ooxooo?oox"

    6

    Returns: 65519

  84. "ox??oxxxxxx??x?xxxo???x?x?x??x??ox?xxx?x"

    2

    Returns: 1

  85. "o??ooo?oo????oooo??o?x?o???xoooo??xoooox"

    3

    Returns: 65535

  86. "ox?x????xx?xxxxx?x?xxxoxx?x?x????xo?o?xx"

    10

    Returns: 0

  87. "oooo??o??oo?ooo?o?x?o??oxo?oo??ox?ooo??x"

    9

    Returns: 65336

  88. "o?o??xx?o??xxx?xx?xxxx?x?x?xo?x?x?x?xx?x"

    9

    Returns: 0

  89. "ooo?o???ooxo?oxo?o?x?o?o????oo??oo?oooox"

    5

    Returns: 65525

  90. "oxx??x?ox???x?x?xx?xxo?xxxxx?x??xx???xox"

    9

    Returns: 0

  91. "ooox?oxoo?o?o???o?o?o??oo?ox???oo??oooox"

    10

    Returns: 64840

  92. "o??????????????????????????????????????x"

    2

    Returns: 143548512057

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: