prithivMLmods/Coder-Stat

1 2<script type="text/x-mathjax-config">3  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});4</script>5<script type='text/javascript' src='http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML'></script>6</script>7 8 9<h2>Problem K10Black and White Boxes11</h2>12 13<p>14Alice and Bob play the following game.15</p>16 17<ol>18<li> There are a number of straight piles of boxes. The boxes have the same size and are painted either black or white.19</li>20 21<li> Two players, namely Alice and Bob, take their turns alternately. Who to play first is decided by a fair random draw.22</li>23 24<li> In Alice's turn, she selects a black box in one of the piles, and removes the box together with all the boxes above it, if any. If no black box to remove is left, she loses the game.25</li>26 27<li> In Bob's turn, he selects a white box in one of the piles, and removes the box together with all the boxes above it, if any. If no white box to remove is left, he loses the game. 28</li>29</ol>30 31<p>32Given an initial configuration of piles and who plays first, the game is a <i>definite perfect information game</i>. In such a game, one of the players has sure win provided he or she plays best. The draw for the first player, thus, essentially decides the winner.33</p>34 35<p>36In fact, this seemingly boring property is common with many popular games, such as chess. The chess game, however, is complicated enough to prevent thorough analyses, even by supercomputers, which leaves us rooms to enjoy playing.37</p>38 39<p>40This game of box piles, however, is not as complicated. The best plays may be more easily found. Thus, initial configurations should be fair, that is, giving both players chances to win. A configuration in which one player can always win, regardless of who plays first, is undesirable.41</p>42 43<p>44You are asked to arrange an initial configuration for this game by picking a number of piles from the given candidate set. As more complicated configuration makes the game more enjoyable, you are expected to find the configuration with the maximum number of boxes among fair ones.45</p>46 47 48<h3>Input</h3>49 50<p>51The input consists of a single test case, formatted as follows.<br/>52<br/>53$n$<br/>54$p_1$<br/>55.<br/>56.<br/>57.<br/>58$p_n$<br/>59</p>60 61<p>62A positive integer $n$ ($\leq 40$) is the number of candidate piles. Each $p_i$ is a string of characters <span>B</span> and <span>W</span>, representing the $i$-th candidate pile. <span>B</span> and <span>W</span> mean black and white boxes, respectively. They appear in the order in the pile, from bottom to top. The number of boxes in a candidate pile does not exceed 40.63</p>64 65<h3>Output</h3>66<p>67Output in a line the maximum possible number of boxes in a fair initial configuration consisting of some of the candidate piles. If only the empty configuration is fair, output a zero.68</p>69 70 71 72<h3>Sample Input 1</h3>73 74<pre>475B76W77WB78WB</pre>79 80<h3>Sample Output 1</h3>81 82<pre>5</pre>83 84<br/>85 86<h3>Sample Input 2</h3>87 88<pre>689B90W91WB92WB93BWW94BWW</pre>95 96<h3>Sample Output 2</h3>97 98<pre>10</pre>