forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBallsSeparating.html
22 lines (22 loc) · 4.97 KB
/
BallsSeparating.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>There are <b>N</b> boxes numbered from 0 to <b>N</b>-1, inclusive. For each i, box i contains <b>red</b>[i] red balls, <b>green</b>[i] green balls, and <b>blue</b>[i] blue balls.
<br></br>
<br></br>
Fox Ciel wants to separate the balls by colors. In each operation, she can pick a single ball from some box and put it into another box. She considers the balls to be separated if no box contains balls of more than one color.
<br></br>
<br></br>
Return the minimal number of operations required to separate the balls. If this is impossible, return -1.
</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>BallsSeparating</td></tr><tr><td>Method:</td><td>minOperations</td></tr><tr><td>Parameters:</td><td>vector <int>, vector <int>, vector <int></td></tr><tr><td>Returns:</td><td>int</td></tr><tr><td>Method signature:</td><td>int minOperations(vector <int> red, vector <int> green, vector <int> blue)</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>red</b>, <b>green</b> and <b>blue</b> will each contain between 1 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>red</b>, <b>green</b> and <b>blue</b> will contain the same number of elements.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>red</b>, <b>green</b> and <b>blue</b> will be between 1 and 1,000,000, 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>{1, 1, 1}</pre></td></tr><tr><td><pre>{1, 1, 1}</pre></td></tr><tr><td><pre>{1, 1, 1}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 6</pre></td></tr><tr><td><table><tr><td colspan="2">One way to separate the balls in six operations is as follows:
<ul>
<li>Move a red ball from box 1 to box 0.</li>
<li>Move a red ball from box 2 to box 0.</li>
<li>Move a green ball from box 0 to box 1.</li>
<li>Move a green ball from box 2 to box 1.</li>
<li>Move a blue ball from box 0 to box 2.</li>
<li>Move a blue ball from box 1 to box 2.</li>
</ul>
The pictures on the left and on the right show the initial and the final states of the balls, respectively.
<br></br>
<br></br>
<img src="http://www.topcoder.com/contest/problem/BallsSeparating/pic1.png"></img>
<img src="http://www.topcoder.com/contest/problem/BallsSeparating/pic2.png"></img></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>{5}</pre></td></tr><tr><td><pre>{6}</pre></td></tr><tr><td><pre>{8}</pre></td></tr></table></td></tr><tr><td><pre>Returns: -1</pre></td></tr><tr><td><table><tr><td colspan="2">It is impossible to separate the balls.</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>{4, 6, 5, 7}</pre></td></tr><tr><td><pre>{7, 4, 6, 3}</pre></td></tr><tr><td><pre>{6, 5, 3, 8}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 37</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>{7, 12, 9, 9, 7}</pre></td></tr><tr><td><pre>{7, 10, 8, 8, 9}</pre></td></tr><tr><td><pre>{8, 9, 5, 6, 13}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 77</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>{842398, 491273, 958925, 849859, 771363, 67803, 184892, 391907, 256150, 75799}</pre></td></tr><tr><td><pre>{268944, 342402, 894352, 228640, 903885, 908656, 414271, 292588, 852057, 889141}</pre></td></tr><tr><td><pre>{662939, 340220, 600081, 390298, 376707, 372199, 435097, 40266, 145590, 505103}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 7230607</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>