WorldPeace
SRM 204 · 2004-07-21 · by vorthys
Problem Statement
You have decided to organize a grassroots campaign for world peace. Your plan
is to assign ordinary citizens into groups of k penpals such that each
group contains citizens from k different countries.
People in each group will
exchange letters in an effort to increase their understanding of each other's
cultures.
Given k and the populations of the participating countries as a
Note that no individual may be assigned to more than one group, and that some individuals may be left without a group.
Constraints
- k is between 2 and 20, inclusive.
- countries contains between k and 50 elements, inclusive.
- Each element of countries is between 1 and 1000000000 (one billion), inclusive.
2
{ 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }
Returns: 5000000000
2
{ 1, 2, 3, 4, 5, 10000 }
Returns: 15
4
{ 4,4,4,4,4 }
Returns: 5
Suppose the countries are Canada, China, Poland, Sweden, and the USA. Then you can make 5 groups as follows: Canada, China, Poland, Sweden Canada, China, Poland, USA Canada, China, Sweden, USA Canada, Poland, Sweden, USA China, Poland, Sweden, USA
5
{ 1,2,3,4,5,6 }
Returns: 3
Suppose the countries are designated 1 through 6, according to population. Then three groups are possible: 2,3,4,5,6 2,3,4,5,6 1,3,4,5,6 There are six people left unassigned, but they come from only three different countries, so they cannot be made into another group.
2
{ 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }
Returns: 3000000000
Submissions are judged against all 42 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WorldPeace with a public method long long numGroups(int k, vector<int> countries) · 42 test cases · 2 s / 256 MB per case