-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCatsOnTheLineDiv2.html
More file actions
18 lines (18 loc) · 5.01 KB
/
CatsOnTheLineDiv2.html
File metadata and controls
18 lines (18 loc) · 5.01 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td><p>
There are some cats sitting on a straight line that goes from the left to the right.
You are given two vector <int>s <b>position</b> and <b>count</b>.
For each valid i, there are <b>count</b>[i] cats initially sitting at the point <b>position</b>[i].
</p>
<p>
</p>
<p>
During each minute, each cat chooses and performs one of three possible actions: it may stay in its place, move one unit to the left (i.e., from x to x-1), or move one unit to the right (i.e., from x to x+1).
(Note that there are no restrictions. In particular, different cats that are currently at the same point may make different choices.)
</p>
<p>
</p>
<p>
You are also given an int <b>time</b>.
The goal is to rearrange the cats in such a way that each point contains at most one cat.
Return "Possible" if it's possible to achive the goal in <b>time</b> minutes, and "Impossible" otherwise (quotes for clarity).
</p></td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>CatsOnTheLineDiv2</td></tr><tr><td>Method:</td><td>getAnswer</td></tr><tr><td>Parameters:</td><td>vector <int>, vector <int>, int</td></tr><tr><td>Returns:</td><td>string</td></tr><tr><td>Method signature:</td><td>string getAnswer(vector <int> position, vector <int> count, int time)</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>256</td></tr></table></td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>position</b> will contain between 1 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>position</b> and <b>count</b> will contain the same number of elements.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>position</b> will be between -1000 and 1000, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>All elements of <b>position</b> will be distinct.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>count</b> will be between 1 and 1000, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>time</b> will be between 0 and 1000, 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>{0}</pre></td></tr><tr><td><pre>{7}</pre></td></tr><tr><td><pre>3</pre></td></tr></table></td></tr><tr><td><pre>Returns: "Possible"</pre></td></tr><tr><td><table><tr><td colspan="2">There are 7 cats sitting at the origin in this case. There are also 7 different points that cats can reach in 3 minutes, so each cat can occupy a unique point. Thus, the answer is "Possible".</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>{0}</pre></td></tr><tr><td><pre>{8}</pre></td></tr><tr><td><pre>2</pre></td></tr></table></td></tr><tr><td><pre>Returns: "Impossible"</pre></td></tr><tr><td><table><tr><td colspan="2">Unlike the first test case, in this case there are 8 cats for 7 available points. Thus, the answer is "Impossible".</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>{0, 1}</pre></td></tr><tr><td><pre>{3, 1}</pre></td></tr><tr><td><pre>0</pre></td></tr></table></td></tr><tr><td><pre>Returns: "Impossible"</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>{5, 0, 2}</pre></td></tr><tr><td><pre>{2, 3, 5}</pre></td></tr><tr><td><pre>2</pre></td></tr></table></td></tr><tr><td><pre>Returns: "Impossible"</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>{5, 1, -10, 7, 12, 2, 10, 20}</pre></td></tr><tr><td><pre>{3, 4, 2, 7, 1, 4, 3, 4}</pre></td></tr><tr><td><pre>6</pre></td></tr></table></td></tr><tr><td><pre>Returns: "Possible"</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>