CentipedeSocks
SRM 757 · 2019-04-28 · by misof
Problem Statement
You have C pet centipedes. You want to take them out for a walk, but it's quite cold. You want to give them socks to make them feel more comfortable.
Each of your centipedes has F feet. You have a large bin with centipede socks. The socks come in different colors, but your centipedes are quite picky and each of them requires to wear F socks of the same color.
You are given the
Find and return the smallest X such that if you take any X socks out of the bin, it is guaranteed that you will be able to use some of them to keep all feet of all your centipedes warm. If there is no such X, return -1 instead.
Constraints
- C will be between 1 and 50, inclusive.
- F will be between 1 and 100, inclusive.
- sockCounts will have between 1 and 100 elements, inclusive.
- Each element of sockCounts will be between 1 and 10^7, inclusive.
1
100
{1, 1, 1, 1, 100}
Returns: 104
One centipede with 100 feet. If you are really unlucky, you need to remove all 104 socks from the bin until you get all 100 pink ones.
1
100
{40, 50, 60, 70}
Returns: -1
You do not have 100 socks of any single color, so the poor centipede will be cold.
3
10
{12345}
Returns: 30
There are 12345 red socks in the bin. You just grab the first 30 and put 10 of them onto each of your centipedes.
2
3
{4, 4, 5}
Returns: 10
Two red, two blue, and five pink socks are still not enough to satisfy two three-legged centipedes.
23
9
{215, 28, 69, 67, 2, 31, 260, 59, 11, 439, 189, 1, 53, 356, 8, 6, 3, 904, 385, 2, 45, 156, 109, 23, 389, 34, 207, 916}
Returns: 397
Submissions are judged against all 171 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CentipedeSocks with a public method int fewestSocks(int C, int F, vector<int> sockCounts) · 171 test cases · 2 s / 256 MB per case