F. Egg Roulette

Codeforces

IDCF865F

Time3000ms

Memory256MB

Difficulty—

bitmasksbrute forcedivide and conquermathmeet-in-the-middle

The game of Egg Roulette is played between two players. Initially 2_R_ raw eggs and 2_C_ cooked eggs are placed randomly into a carton. The shells are left on so there is no way to distinguish a raw egg from a cooked egg. One at a time, a player will select an egg, and then smash the egg on his/her forehead. If the egg was cooked, not much happens, but if the egg was raw, it will make quite the mess. This continues until one player has broken _R_ raw eggs, at which point that player is declared the loser and the other player wins. The order in which players take turns can be described as a string of '_A_' and '_B_' characters, where the _i_\-th character tells which player should choose the _i_\-th egg. Traditionally, players take turns going one after the other. That is, they follow the ordering "_ABABAB..._". This isn't very fair though, because the second player will win more often than the first. We'd like you to find a better ordering for the players to take their turns. Let's define the unfairness of an ordering as the absolute difference between the first player's win probability and the second player's win probability. We're interested in orderings that minimize the unfairness. We only consider an ordering valid if it contains the same number of '_A_'s as '_B_'s. You will also be given a string _S_ of length 2(_R_ + _C_) containing only '_A_', '_B_', and '_?_' characters. An ordering is said to match _S_ if it only differs from _S_ in positions where _S_ contains a '_?_'. Of the valid orderings that minimize unfairness, how many match _S_? ## Input The first line of input will contain integers _R_ and _C_ (1 ≤ _R_, _C_ ≤ 20, _R_ + _C_ ≤ 30). The second line of input will contain the string _S_ of length 2(_R_ + _C_) consisting only of characters '_A_', '_B_', '_?_'. ## Output Print the number of valid orderings that minimize unfairness and match _S_. [samples] ## Note In the first test case, the minimum unfairness is 0, and the orderings that achieve it are "_ABBA_" and "_BAAB_", neither of which match _S_. Note that an ordering such as "_ABBB_" would also have an unfairness of 0, but is invalid because it does not contain the same number of '_A_'s as '_B_'s. In the second example, the only matching ordering is "_BBAAABABABBA_".

Samples

Input #1

1 1
??BB

Output #1

Input #2

2 4
?BA??B??A???

Output #2

Input #3

4 14
????A??BB?????????????AB????????????

Output #3

API Response (JSON)

{
  "problem": {
    "name": "F. Egg Roulette",
    "description": {
      "content": "The game of Egg Roulette is played between two players. Initially 2_R_ raw eggs and 2_C_ cooked eggs are placed randomly into a carton. The shells are left on so there is no way to distinguish a raw e",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF865F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The game of Egg Roulette is played between two players. Initially 2_R_ raw eggs and 2_C_ cooked eggs are placed randomly into a carton. The shells are left on so there is no way to distinguish a raw e...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments