SharksDinner
SRM 358 · 2007-07-17 · by icanadi
SRM 358 · 2007-07-17 · by icanadi · Graph Theory
Problem Statement
Problem Statement
Some sharks are having dinner and they are eating each other. For every shark we know its size, speed and intelligence (measured in positive integers). Shark A can eat shark B if and only if A's size, speed and intelligence are all greater than or equal to B's. Due to digestive restrictions, each shark can eat at most two other sharks.
Givenint[] size, int[] speed and int[] intelligence, return the minimum number of sharks that will survive.
Given
Constraints
- size, speed and intelligence will contain the same number of elements.
- size, speed and intelligence will each contain between 1 and 50 elements, inclusive.
- Each element of size, speed and intelligence will be between 1 and 2,000,000,000, inclusive.
Examples
0)
{ 1, 4, 3 }
{ 2, 3, 1 }
{ 1, 5, 2 }
Returns: 1
Shark 1 eats sharks 0 and 2 so we get 1 survivor.
1)
{ 4, 10, 5, 8, 8 }
{ 5, 10, 7, 7, 10 }
{ 5, 8, 10, 7, 3 }
Returns: 2
Shark 2 eats shark 0, and shark 1 eats sharks 3 and 4.
2)
{ 1, 2, 3, 4, 100 }
{ 4, 3, 2, 1, 100 }
{ 2, 4, 1, 3, 100 }
Returns: 3
The big shark eats two of the smaller sharks and is not hungry anymore, so the other two of the smaller sharks are lucky (and they cannot eat each other).
3)
{ 4, 4, 4, 4 }
{ 3, 3, 3, 3 }
{ 8, 8, 8, 8 }
Returns: 1
Sharks with the same level of speed, size and intelligence can eat each other.
4)
{9,5,8,3,8,5,3,2,6,9,8,2,7,1,1,2,1,6,6,5,5,6,2,6,1,6,7,2,7,8,3,4,3,8,6,1,3,8,9,8,8,6,8,3,4,6,2,3,9,8}
{7,5,4,7,1,4,1,5,3,7,1,3,9,1,2,5,9,4,2,8,1,7,2,6,9,4,2,9,6,2,7,1,4,1,7,2,3,5,5,3,1,5,6,9,6,7,4,5,8,3}
{1,8,9,1,2,9,4,4,8,7,3,3,7,6,1,3,5,1,7,9,4,7,3,7,6,8,4,8,1,2,1,8,8,1,8,9,7,9,1,3,6,3,5,2,6,3,4,9,4,1}
Returns: 7
Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SharksDinner with a public method int minSurvivors(vector<int> size, vector<int> speed, vector<int> intelligence) · 72 test cases · 2 s / 256 MB per case