prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem B:</font> Make a Sequence</H1>3 4<p>5Your company’s next product will be a new game, which is a three-dimensional variant of the6classic game “Tic-Tac-Toe”. Two players place balls in a three-dimensional space (board), and7try to make a sequence of a certain length.8</p>9<p>10People believe that it is fun to play the game, but they still cannot fix the values of some11parameters of the game. For example, what size of the board makes the game most exciting?12Parameters currently under discussion are the board size (we call it <i>n</i> in the following) and the13length of the sequence (<i>m</i>). In order to determine these parameter values, you are requested to14write a computer simulator of the game.15</p>16<p>17You can see several snapshots of the game in Figures 1-3. These figures correspond to the three18datasets given in the Sample Input.19</p>20 21<center>22<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_makeASequence1">23<p>Figure 1: A game with <i>n</i> = <i>m</i> = 3</p>24</center>25 26<p>27Here are the precise rules of the game.28</p>29 30<ol>31  <li> Two players, Black and White, play alternately. Black plays first.</li>32  <li> There are <i>n</i> &times; <i>n</i> vertical pegs. Each peg can accommodate up to <i>n</i> balls. A peg can be33     specified by its <i>x</i>- and <i>y</i>-coordinates (1 &le; <i>x</i>, <i>y</i> &le; <i>n</i>). A ball on a peg can be specified by34     its <i>z</i>-coordinate (1 &le; <i>z</i> &le; <i>n</i>). At the beginning of a game, there are no balls on any of the35     pegs.</li>36 37<br>38<center>39<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_makeASequence2">40<p>Figure 2: A game with <i>n</i> = <i>m</i> = 3 (White made a 3-sequence before Black)</p>41</center>42 43<li>   On his turn, a player chooses one of <i>n</i> &times; <i>n</i> pegs, and puts a ball of his color onto the peg.44   The ball follows the law of gravity. That is, the ball stays just above the top-most ball45   on the same peg or on the floor (if there are no balls on the peg). Speaking differently, a46   player can choose <i>x</i>- and <i>y</i>-coordinates of the ball, but he cannot choose its <i>z</i>-coordinate.</li>47<li> The objective of the game is to make an <i>m</i>-sequence. If a player makes an <i>m</i>-sequence or48   longer of his color, he wins. An <i>m</i>-sequence is a row of <i>m</i> consecutive balls of the same49   color. For example, black balls in positions (5, 1, 2), (5, 2, 2) and (5, 3, 2) form a 3-sequence.50   A sequence can be horizontal, vertical, or diagonal. Precisely speaking, there are 1351   possible directions to make a sequence, categorized as follows.</li>52 53<br>54<center>55<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_makeASequence3">56<p>Figure 3: A game with <i>n</i> = 4, <i>m</i> = 3 (Black made two 4-sequences)</p>57</center>58 59<p>60(a) One-dimensional axes. For example, (3, 1, 2), (4, 1, 2) and (5, 1, 2) is a 3-sequence.61  There are three directions in this category.<br>62(b) Two-dimensional diagonals. For example, (2, 3, 1), (3, 3, 2) and (4, 3, 3) is a 3-sequence.63    There are six directions in this category.<br>64(c) Three-dimensional diagonals. For example, (5, 1, 3), (4, 2, 4) and (3, 3, 5) is a 3-65    sequence. There are four directions in this category.66</p>67 68 69<p>Note that we do not distinguish between opposite directions.</p>70 71</ol>72 73 74<p>75As the evaluation process of the game, people have been playing the game several times changing76the parameter values. You are given the records of these games. It is your job to write a computer77program which determines the winner of each recorded game.78</p>79<p>80Since it is difficult for a human to find three-dimensional sequences, players often do not notice81the end of the game, and continue to play uselessly. In these cases, moves after the end of the82game, i.e. after the winner is determined, should be ignored. For example, after a player won83making an <i>m</i>-sequence, players may make additional <i>m</i>-sequences. In this case, all <i>m</i>-sequences84but the first should be ignored, and the winner of the game is unchanged.85</p>86<p>87A game does not necessarily end with the victory of one of the players. If there are no pegs left88to put a ball on, the game ends with a draw. Moreover, people may quit a game before making89any m-sequence. In such cases also, the game ends with a draw.90</p>91 92 93 94<H2>Input</H2>95 96<p>97The input consists of multiple datasets each corresponding to the record of a game. A dataset98starts with a line containing three positive integers <i>n</i>, <i>m</i>, and <i>p</i> separated by a space. The99relations 3 &le; <i>m</i> &le; <i>n</i> &le; 7 and 1 &le; <i>p</i> &le; <i>n</i><sup>3</sup> hold between them. <i>n</i> and <i>m</i> are the parameter values100of the game as described above. <i>p</i> is the number of moves in the game.101</p>102<p>103The rest of the dataset is <i>p</i> lines each containing two positive integers <i>x</i> and <i>y</i>. Each of these104lines describes a move, i.e. the player on turn puts his ball on the peg specified. You can assume105that 1 &le; <i>x</i> &le; <i>n</i> and 1 &le; <i>y</i> &le; <i>n</i>. You can also assume that at most n balls are put on a peg106throughout a game.107</p>108<p>109The end of the input is indicated by a line with three zeros separated by a space.110</p>111 112<H2>Output</H2>113 114<p>115For each dataset, a line describing the winner and the number of moves until the game ends116should be output. The winner is either “Black” or “White”. A single space should be inserted117between the winner and the number of moves. No other extra characters are allowed in the118output.119</p>120<p>121In case of a draw, the output line should be “Draw”.122</p>123 124<H2>Sample Input</H2>125<pre>1263 3 31271 11281 11291 11303 3 71312 21321 31331 11342 31352 11363 31373 11384 3 151391 11402 21411 11423 31433 31441 11453 31463 31474 41481 11494 41504 41514 41524 11532 21540 0 0155</pre>156 157<H2>Output for the Sample Input</H2>158<pre>159Draw160White 6161Black 15162</pre>163 164