IdenticalBags
TCO19 SRM 750 · 2019-01-09 · by misof
Problem Statement
You are preparing for Halloween. You like to hand out bags of candy. In order to prevent arguments between the kids who get them, you want all bags to be identical.
You have a supply of various candy. Each element of candy is the number of pieces of a specific candy type. You want to create bags that will contain bagSize pieces of candy each. Compute and return the maximum number of identical bags you can make.
Constraints
- candy will contain between 1 and 100 elements, inclusive.
- Each element of candy will be between 1 and 10^18, inclusive.
- bagSize will be between 1 and 10^18, inclusive.
{10, 11, 12}
3
Returns: 10
You can make 10 identical bags, each containing one candy of each type.
{10, 11, 12, 1, 2, 3}
3
Returns: 10
We have a few more candy types than in Example #0, but the optimal solution remained the same.
{100}
7
Returns: 14
This time you can make (100 div 7) bags, each containing 7 candies of the only type you have.
{10000000000, 20000000000, 30000000000}
6
Returns: 10000000000
Watch out for integer overflow.
{1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000}
1
Returns: 1000000000000000000
Submissions are judged against all 126 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IdenticalBags with a public method long long makeBags(vector<long long> candy, long long bagSize) · 126 test cases · 2 s / 256 MB per case