English · Original
Chinese · Translation
Formal · Original
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_".
鸡蛋轮盘赌游戏由两名玩家进行。初始时，有 #cf_span[2R] 个生鸡蛋和 #cf_span[2C] 个熟鸡蛋被随机放入一个蛋盒中。蛋壳保留，因此无法区分生蛋与熟蛋。玩家轮流依次选取一个鸡蛋，然后将其砸在自己的额头上。如果鸡蛋是熟的，几乎不会发生什么；但如果鸡蛋是生的，就会造成很大的混乱。游戏持续进行，直到某位玩家砸碎了 #cf_span[R] 个生鸡蛋，此时该玩家被判为输家，另一位玩家获胜。
玩家轮流的顺序可以用一个由 '_A_' 和 '_B_' 字符组成的字符串描述，其中第 #cf_span[i] 个字符表示第 #cf_span[i] 个鸡蛋应由哪位玩家选取。传统上，玩家轮流进行，即遵循 "_ABABAB..._" 的顺序。但这并不公平，因为第二位玩家获胜的概率更高。我们希望你找到一种更公平的轮流顺序。我们将一种顺序的不公平性定义为第一位玩家获胜概率与第二位玩家获胜概率之差的绝对值。我们关注那些最小化不公平性的顺序。我们仅考虑包含相同数量 '_A_' 和 '_B_' 的顺序为有效顺序。
你还将获得一个长度为 #cf_span[2(R + C)] 的字符串 #cf_span[S]，仅包含 '_A_'、'_B_' 和 '_?_' 字符。若一种顺序仅在 #cf_span[S] 含 '_?_' 的位置上与之不同，则称该顺序与 #cf_span[S] 匹配。在所有最小化不公平性的有效顺序中，有多少个与 #cf_span[S] 匹配？
输入的第一行包含整数 #cf_span[R] 和 #cf_span[C] #cf_span[(1 ≤ R, C ≤ 20, R + C ≤ 30)]。
输入的第二行包含长度为 #cf_span[2(R + C)] 的字符串 #cf_span[S]，仅由字符 '_A_'、'_B_'、'_?_' 组成。
请输出满足最小不公平性且与 #cf_span[S] 匹配的有效顺序的数量。
在第一个测试用例中，最小不公平性为 #cf_span[0]，达到该值的顺序为 "_ABBA_" 和 "_BAAB_"，二者均不匹配 #cf_span[S]。请注意，像 "_ABBB_" 这样的顺序虽然不公平性也为 #cf_span[0]，但无效，因为它不包含相同数量的 '_A_' 和 '_B_'。
在第二个示例中，唯一匹配的顺序是 "_BBAAABABABBA_"。
## Input
输入的第一行包含整数 #cf_span[R] 和 #cf_span[C] #cf_span[(1 ≤ R, C ≤ 20, R + C ≤ 30)]。输入的第二行包含长度为 #cf_span[2(R + C)] 的字符串 #cf_span[S]，仅由字符 '_A_'、'_B_'、'_?_' 组成。
## Output
请输出满足最小不公平性且与 #cf_span[S] 匹配的有效顺序的数量。
[samples]
## Note
在第一个测试用例中，最小不公平性为 #cf_span[0]，达到该值的顺序为 "_ABBA_" 和 "_BAAB_"，二者均不匹配 #cf_span[S]。请注意，像 "_ABBB_" 这样的顺序虽然不公平性也为 #cf_span[0]，但无效，因为它不包含相同数量的 '_A_' 和 '_B_'。在第二个示例中，唯一匹配的顺序是 "_BBAAABABABBA_"。
**Definitions**
Let $ R, C \in \mathbb{Z}^+ $ with $ 1 \leq R, C \leq 20 $, $ R + C \leq 30 $.
Let $ N = 2(R + C) $.
Let $ S \in \{A, B, ?\}^N $ be a constraint string.
A *valid ordering* is a string $ T \in \{A, B\}^N $ such that:
- $ T $ contains exactly $ R + C $ occurrences of $ A $ and $ R + C $ occurrences of $ B $.
- $ T $ matches $ S $: for all $ i \in \{1, \dots, N\} $, if $ S_i \neq ? $, then $ T_i = S_i $.
Let $ \mathcal{T} $ be the set of all valid orderings.
For each $ T \in \mathcal{T} $, define the *win probability* of player $ A $ as $ P_A(T) $, and of player $ B $ as $ P_B(T) = 1 - P_A(T) $, under the following game:
- $ R $ raw eggs and $ C $ cooked eggs are randomly permuted in a sequence.
- Players alternate selecting eggs in order $ T_1, T_2, \dots, T_N $.
- The first player to have broken $ R $ raw eggs loses.
- $ P_A(T) $: probability that player $ B $ loses (i.e., player $ A $ wins).
Define *unfairness* of $ T $ as $ U(T) = |P_A(T) - P_B(T)| = |2P_A(T) - 1| $.
Let $ U_{\min} = \min_{T \in \mathcal{T}} U(T) $.
**Objective**
Count the number of valid orderings $ T \in \mathcal{T} $ such that $ U(T) = U_{\min} $.
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": "CF866F"
},
"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"
},
{
"statement_type": "Markdown",
"content": "鸡蛋轮盘赌游戏由两名玩家进行。初始时，有 #cf_span[2R] 个生鸡蛋和 #cf_span[2C] 个熟鸡蛋被随机放入一个蛋盒中。蛋壳保留，因此无法区分生蛋与熟蛋。玩家轮流依次选取一个鸡蛋，然后将其砸在自己的额头上。如果鸡蛋是熟的，几乎不会发生什么；但如果鸡蛋是生的，就会造成很大的混乱。游戏持续进行，直到某位玩家砸碎了 #cf_span[R] 个生鸡蛋，此时该玩家被判为输家，另一位玩家获胜。...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ R, C \\in \\mathbb{Z}^+ $ with $ 1 \\leq R, C \\leq 20 $, $ R + C \\leq 30 $. \nLet $ N = 2(R + C) $. \nLet $ S \\in \\{A, B, ?\\}^N $ be a constraint string. \n\nA *valid ordering* is ...",
"is_translate": false,
"language": "Formal"
}
]
}