forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathPaperAndPaintEasy.html
19 lines (15 loc) · 6.51 KB
/
PaperAndPaintEasy.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>Onise likes to play with paper and paint. He has a piece of paper with dimensions <b>width</b> x <b>height</b>. He does the following steps with the paper:
<ol>
<li>Fold the paper along the line x = <b>xfold</b> (the left side of the paper is folded over the right side).</li>
<li>Divide the paper vertically into <b>cnt</b>+1 equal sections. Then, <b>cnt</b> times, take the topmost section and fold it over the section below it.</li>
<li>Paint a rectangle with the lower-left corner at (<b>x1</b>, <b>y1</b>) and the upper-right corner at (<b>x2</b>, <b>y2</b>). Note that (0, 0) is now the lower-left corner of the paper in its current folded state, not its original state. The paint will seep through all the layers of the folded paper. See the image below for clarification.</li>
<li>Unfold the paper.</li>
</ol>
For example, let's say Onise has a piece of paper that is 5 x 6. He performs the described steps where <b>xfold</b> is 2, <b>cnt</b> is 2, and the coordinates of the painted rectangle's corners are (1, 1) and (3, 2). The following will happen (note that the paper starts out blue in the images and gets painted white):
<center><img src="http://www.topcoder.com/contest/problem/PaperAndPaint/1.png"></img>
<img src="http://www.topcoder.com/contest/problem/PaperAndPaint/2.png"></img>
<img src="http://www.topcoder.com/contest/problem/PaperAndPaint/3.png"></img>
<img src="http://www.topcoder.com/contest/problem/PaperAndPaint/4.png"></img>
<img src="http://www.topcoder.com/contest/problem/PaperAndPaint/5.png"></img>
<img src="http://www.topcoder.com/contest/problem/PaperAndPaint/6.png"></img></center><br></br><br></br>
You are given ints <b>width</b> and <b>height</b>, and ints <b>xfold</b>, <b>cnt</b>, <b>x1</b>, <b>y1</b>, <b>x2</b> and <b>y2</b>. Return the total area of of the paper that is not covered in paint after Onise is done.</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>PaperAndPaintEasy</td></tr><tr><td>Method:</td><td>computeArea</td></tr><tr><td>Parameters:</td><td>int, int, int, int, int, int, int, int</td></tr><tr><td>Returns:</td><td>long long</td></tr><tr><td>Method signature:</td><td>long long computeArea(int width, int height, int xfold, int cnt, int x1, int y1, int x2, int y2)</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>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>width</b> and <b>height</b> will be between 1 and 10^9, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>xfold</b> will be between 0 and <b>width</b>, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>cnt</b> will be between 0 and 1000, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>cnt</b>+1 will be a divisor of <b>height</b>.</td></tr><tr><td align="center" valign="top">-</td><td>0 <= <b>x1</b> < <b>x2</b> <= max(<b>xfold</b>, <b>width</b>-<b>xfold</b>) and 0 <= <b>y1</b> < <b>y2</b> <= <b>height</b>/(<b>cnt</b>+1).</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>5</pre></td></tr><tr><td><pre>6</pre></td></tr><tr><td><pre>2</pre></td></tr><tr><td><pre>2</pre></td></tr><tr><td><pre>1</pre></td></tr><tr><td><pre>1</pre></td></tr><tr><td><pre>3</pre></td></tr><tr><td><pre>2</pre></td></tr></table></td></tr><tr><td><pre>Returns: 21</pre></td></tr><tr><td><table><tr><td colspan="2">The example from the problem statement.</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>13</pre></td></tr><tr><td><pre>1</pre></td></tr><tr><td><pre>0</pre></td></tr><tr><td><pre>1</pre></td></tr><tr><td><pre>8</pre></td></tr><tr><td><pre>2</pre></td></tr><tr><td><pre>12</pre></td></tr></table></td></tr><tr><td><pre>Returns: 35</pre></td></tr><tr><td></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>12</pre></td></tr><tr><td><pre>12</pre></td></tr><tr><td><pre>7</pre></td></tr><tr><td><pre>3</pre></td></tr><tr><td><pre>3</pre></td></tr><tr><td><pre>1</pre></td></tr><tr><td><pre>6</pre></td></tr><tr><td><pre>2</pre></td></tr></table></td></tr><tr><td><pre>Returns: 124</pre></td></tr><tr><td></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>4</pre></td></tr><tr><td><pre>5</pre></td></tr><tr><td><pre>4</pre></td></tr><tr><td><pre>0</pre></td></tr><tr><td><pre>0</pre></td></tr><tr><td><pre>0</pre></td></tr><tr><td><pre>1</pre></td></tr><tr><td><pre>1</pre></td></tr></table></td></tr><tr><td><pre>Returns: 19</pre></td></tr><tr><td></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>4</pre></td></tr><tr><td><pre>8</pre></td></tr><tr><td><pre>4</pre></td></tr><tr><td><pre>3</pre></td></tr><tr><td><pre>0</pre></td></tr><tr><td><pre>1</pre></td></tr><tr><td><pre>2</pre></td></tr><tr><td><pre>2</pre></td></tr></table></td></tr><tr><td><pre>Returns: 24</pre></td></tr><tr><td></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>4</pre></td></tr><tr><td><pre>8</pre></td></tr><tr><td><pre>3</pre></td></tr><tr><td><pre>0</pre></td></tr><tr><td><pre>1</pre></td></tr><tr><td><pre>1</pre></td></tr><tr><td><pre>3</pre></td></tr><tr><td><pre>2</pre></td></tr></table></td></tr><tr><td><pre>Returns: 30</pre></td></tr><tr><td></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>