forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathHyperKnight.html
9 lines (9 loc) · 6.58 KB
/
HyperKnight.html
1
2
3
4
5
6
7
8
9
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>Fernando loves to play chess. One day he decided to play chess on an unusually large rectangular board. To compensate for the board's size he also decided to change the distance a knight can move in a single jump.
<br></br><br></br>
To describe the moves easily, we will now introduce a coordinate system. Each cell of the chessboard can be described using two integers (r,c): its row number and its column number. Now, if we have a piece at (r,c), the move (x,y) takes the piece to the cell (r+x,c+y).
<br></br><br></br>
The new chess piece will be called an (<b>a</b>,<b>b</b>)-hyperknight. The hyperknight always has 8 possible moves: (+<b>a</b>,+<b>b</b>), (+<b>a</b>,-<b>b</b>), (-<b>a</b>,+<b>b</b>), (-<b>a</b>,-<b>b</b>), (+<b>b</b>,+<b>a</b>), (+<b>b</b>,-<b>a</b>), (-<b>b</b>,+<b>a</b>), and (-<b>b</b>,-<b>a</b>). Note that the original chess knight is a (2,1)-hyperknight.
<br></br><br></br>
Of course, as the chessboard is finite, it is not always possible to make each of the 8 moves. Some of them may cause our hyperknight to leave the chessboard. A move is called <i>valid</i> if the destination cell is on the chessboard. Fernando would like to know the number of cells on his board such that his hyperknight will have exactly <b>k</b> valid moves from that cell.
<br></br><br></br>
You are given the ints <b>a</b>, <b>b</b>, <b>numRows</b>, <b>numColumns</b> and <b>k</b>. The values <b>numRows</b> and <b>numColumns</b> define the number of rows and number of columns on the chessboard, respectively. The other three values were already explained above. Compute and return the number of cells on the chessboard that have exactly <b>k</b> valid (<b>a</b>,<b>b</b>)-hyperknight moves.</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>HyperKnight</td></tr><tr><td>Method:</td><td>countCells</td></tr><tr><td>Parameters:</td><td>int, int, int, int, int</td></tr><tr><td>Returns:</td><td>long long</td></tr><tr><td>Method signature:</td><td>long long countCells(int a, int b, int numRows, int numColumns, int k)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td colspan="2"><h3>Limits</h3></td></tr><tr><td>    </td><td><table><tr><td>Time limit (s):</td><td>2.000</td></tr><tr><td>Memory limit (MB):</td><td>64</td></tr></table></td></tr><tr><td colspan="2"><h3>Notes</h3></td></tr><tr><td align="center" valign="top">-</td><td>If you wish, you may assume that the rows are numbered 0 through <b>numRows</b>-1 and columns 0 through <b>numColumns</b>-1. However, note that the actual row/column numbers do not matter, as long as they are consecutive.</td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>a</b> will be between 1 and 1,000,000,000 (10^9), inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>b</b> will be between 1 and 1,000,000,000 (10^9), inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>a</b> will not be equal to <b>b</b>.</td></tr><tr><td align="center" valign="top">-</td><td><b>numRows</b> will be between 1 and 1,000,000,000 (10^9), inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>numColumns</b> will be between 1 and 1,000,000,000 (10^9), inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>2*max(<b>a</b>,<b>b</b>) will be strictly less than min(<b>numRows</b>,<b>numColumns</b>).</td></tr><tr><td align="center" valign="top">-</td><td><b>k</b> will be between 0 and 8, inclusive.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>2</pre></td></tr><tr><td><pre>1</pre></td></tr><tr><td><pre>8</pre></td></tr><tr><td><pre>8</pre></td></tr><tr><td><pre>4</pre></td></tr></table></td></tr><tr><td><pre>Returns: 20</pre></td></tr><tr><td><table><tr><td colspan="2">This is a standard chessboard. We have a traditional chess knight and we are looking for cells such that the knight has exactly 4 valid moves.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>3</pre></td></tr><tr><td><pre>2</pre></td></tr><tr><td><pre>8</pre></td></tr><tr><td><pre>8</pre></td></tr><tr><td><pre>2</pre></td></tr></table></td></tr><tr><td><pre>Returns: 16</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>1</pre></td></tr><tr><td><pre>3</pre></td></tr><tr><td><pre>7</pre></td></tr><tr><td><pre>11</pre></td></tr><tr><td><pre>0</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>3</pre></td></tr><tr><td><pre>2</pre></td></tr><tr><td><pre>10</pre></td></tr><tr><td><pre>20</pre></td></tr><tr><td><pre>8</pre></td></tr></table></td></tr><tr><td><pre>Returns: 56</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>1</pre></td></tr><tr><td><pre>4</pre></td></tr><tr><td><pre>100</pre></td></tr><tr><td><pre>10</pre></td></tr><tr><td><pre>6</pre></td></tr></table></td></tr><tr><td><pre>Returns: 564</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">5)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>2</pre></td></tr><tr><td><pre>3</pre></td></tr><tr><td><pre>1000000000</pre></td></tr><tr><td><pre>1000000000</pre></td></tr><tr><td><pre>8</pre></td></tr></table></td></tr><tr><td><pre>Returns: 999999988000000036</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. </p></body></html>