forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathWorldPeace.html
38 lines (37 loc) · 4.92 KB
/
WorldPeace.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td><p>
You have decided to organize a grassroots campaign for world peace. Your plan
is to assign ordinary citizens into groups of <b>k</b> penpals such that each
group contains citizens from <b>k</b> different countries.
People in each group will
exchange letters in an effort to increase their understanding of each other's
cultures.
Given <b>k</b> and the populations of the participating countries as a
vector <int> <b>countries</b>, you must determine the maximum number of
groups that can be formed.
</p>
<p>
Note that no individual may be assigned to more than one group, and that
some individuals may be left without a group.
</p>
</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>WorldPeace</td></tr><tr><td>Method:</td><td>numGroups</td></tr><tr><td>Parameters:</td><td>int, vector <int></td></tr><tr><td>Returns:</td><td>long long</td></tr><tr><td>Method signature:</td><td>long long numGroups(int k, vector <int> countries)</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>k</b> is between 2 and 20, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>countries</b> contains between <b>k</b> and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>countries</b> is between 1 and 1000000000 (one billion), 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>4</pre></td></tr><tr><td><pre>{ 4,4,4,4,4 }</pre></td></tr></table></td></tr><tr><td><pre>Returns: 5</pre></td></tr><tr><td><table><tr><td colspan="2">Suppose the countries are Canada, China, Poland, Sweden, and the USA. Then you can
make 5 groups as follows:
<pre>
Canada, China, Poland, Sweden
Canada, China, Poland, USA
Canada, China, Sweden, USA
Canada, Poland, Sweden, USA
China, Poland, Sweden, USA
</pre></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>{ 1,2,3,4,5,6 }</pre></td></tr></table></td></tr><tr><td><pre>Returns: 3</pre></td></tr><tr><td><table><tr><td colspan="2">Suppose the countries are designated 1 through 6, according to population. Then three groups are possible:
<pre>
2,3,4,5,6
2,3,4,5,6
1,3,4,5,6
</pre>
There are six people left unassigned, but they come from only three different
countries, so they cannot be made into another group.</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>2</pre></td></tr><tr><td><pre>{ 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }</pre></td></tr></table></td></tr><tr><td><pre>Returns: 3000000000</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>7</pre></td></tr><tr><td><pre>{ 96, 17, 32, 138, 112, 50, 7, 19, 412, 23, 14, 50, 47, 343, 427, 22, 39 }</pre></td></tr></table></td></tr><tr><td><pre>Returns: 166</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>10</pre></td></tr><tr><td><pre>{ 638074479, 717901019, 910893151, 924124222, 991874870, 919392444, 729973192, 607898881,
838529741, 907090878, 632877562, 678638852, 749258866, 949661738, 784641190, 815740520,
689809286, 711327114, 658017649, 636727234, 871088534, 964608547, 867960437, 964911023,
642411618, 868318236, 793328473, 849540177, 960039699, 998262224, 775720601, 634685437,
743766982, 826321850, 846671921, 712570181, 676890302, 814283264, 958273130, 899003369,
909973864, 921987721, 978601888, 633027021, 896400011, 725078407, 662183572, 629843174,
617774786, 695823011 }</pre></td></tr></table></td></tr><tr><td><pre>Returns: 3983180234</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>