hackercupai/hackercup

1<p>2Uriel is an android programmed for a singular purpose &mdash; to obtain jam. He's found himself in a row of cells, some of which hopefully contain raspberry jam for him to gather 3in the form of special jars called "jammers".4</p>5 6<p>7There are |<strong>C</strong>| cells in the row, and their contents are described by a string <strong>C</strong>, with the <em>i</em>th character of <strong>C</strong> 8corresponding to the <em>i</em>th cell. Each character is one of the following:9</p>10 11<ul>12<li> - "<code>.</code>": Empty cell </li>13<li> - "<code>*</code>": Cell initially containing a jammer </li>14<li> - "<code>#</code>": Cell containing a laser barrier </li>15</ul>16  17<p>18By default, each laser barrier is "active". However, whenever a laser barrier has at least one jammer in an adjacent cell to its left or right, that laser barrier becomes jammed by the jammer's jam,19and becomes "inactive" instead. A laser barrier may switch back and forth between being inactive and active if jammers next to it are added or removed. 20A single jammer may be responsible for jamming multiple laser barriers at once.21</p>22  23<p>24Uriel begins in the first cell (which is guaranteed to be empty). He has the ability to carry around any number of jammers at once, though he initially has 0 of them. 25At each point in time, he may choose to perform one of the following actions:26</p>27 28<ul>29<li> - Pick up a jammer from his current cell. He may only do so if the cell contains a jammer. That cell will then become empty.</li>30<li> - Place one of his jammers into his current cell. He may only do so if he's holding at least one jammer, and if the cell is currently completely empty 31(it doesn't contain another jammer, and doesn't contain a laser barrier, even if it's inactive).</li>32<li> - Walk left or right into an adjacent cell, without leaving the row of cells. He may only do so if that cell doesn't currently contain an active laser barrier.</li>33</ul>34  35<p>36Uriel isn't interested in consuming any jam, he just wants to hold onto it &mdash; onto as much of it as he can. 37As such, he'd like to determine the maximum number of jammers which he can ever end up holding at a single time, after performing any number of moves of his choice.38</p>39 40 41<h3>Input</h3>42 43<p>44Input begins with an integer <strong>T</strong>, the number of rows of cells.45For each row of cells, there is a single line containing the string <strong>C</strong> as described above.46</p>47 48 49<h3>Output</h3>50 51<p>52For the <em>i</em>th row of cells, output a line containing "Case #<em>i</em>: " followed by the maximum number of jammers which Uriel can end up holding at once.53</p>54 55 56<h3>Constraints</h3>57 58<p>591 &le; <strong>T</strong> &le; 100 <br />601 &le; |<strong>C</strong>| &le; 400,000 <br />61</p>62 63 64<h3>Explanation of Sample</h3>65 66<p>67In the first case, there are no laser barriers, so Uriel can simply walk to the right while picking up each jammer he comes across, allowing him to end up with 5 jammers by the end.68</p>69 70<p>71In the second case, Uriel is immediately left with no valid moves, as there's an active laser barrier to his right and he's not holding any jammers.72</p>73 74<p>75In the third case, the first laser barrier which Uriel encounters is already inactive due to the jammer to its right, meaning that he can walk through it. 76The second laser barrier is initially active, but Uriel can jam it by putting down a jammer to its left. After collecting the rightmost jammer, Uriel can return to pick up the jammer that he previously put down to end up with all 5 jammers simultaneously in his possession.77</p>78 79 80