EelAndRabbit
SRM 580 · 2012-12-13 · by snuke
SRM 580 · 2012-12-13 · by snuke · Brute Force
Problem Statement
Problem Statement
Rabbit went to a river to catch eels.
All eels are currently swimming down the stream at the same speed.
Rabbit is standing by the river, downstream from all the eels.
Each point on the river has a coordinate. The coordinates increase as we go down the stream. Initially, Rabbit is standing at the origin, and all eels have non-positive coordinates.
You are given twoint[] s: l and t.
These describe the current configuration of eels.
The speed of each eel is 1 (one).
For each i, the length of eel number i is l[i].
The head of eel number i will arrive at the coordinate 0 precisely at the time t[i].
Therefore, at any time T the eel number i has its head at the coordinate T-t[i], and its tail at the coordinate T-t[i]-l[i].
Rabbit may only catch an eel when some part of the eel (between head and tail, inclusive) is at the same coordinate as the rabbit. Rabbit can catch eels at most twice. Each time he decides to catch eels, he may catch as many of the currently available eels as he wants. (That is, he can only catch eels that are in front of him at that instant, and he is allowed and able to catch multiple eels at once.)
Return the maximal total number of eels Rabbit can catch.
Each point on the river has a coordinate. The coordinates increase as we go down the stream. Initially, Rabbit is standing at the origin, and all eels have non-positive coordinates.
You are given two
Rabbit may only catch an eel when some part of the eel (between head and tail, inclusive) is at the same coordinate as the rabbit. Rabbit can catch eels at most twice. Each time he decides to catch eels, he may catch as many of the currently available eels as he wants. (That is, he can only catch eels that are in front of him at that instant, and he is allowed and able to catch multiple eels at once.)
Return the maximal total number of eels Rabbit can catch.
Constraints
- l will contain between 1 and 50 elements, inclusive.
- Each element of l will be between 1 and 1,000,000,000, inclusive.
- l and t will contain the same number of elements.
- Each element of t will be between 0 and 1,000,000,000, inclusive.
Examples
0)
{2, 4, 3, 2, 2, 1, 10}
{2, 6, 3, 7, 0, 2, 0}
Returns: 6
Rabbit can catch 6 eels in the following way: At time 2, catch Eel 0, Eel 4, Eel 5, and Eel 6. At time 8, catch Eel 1 and Eel 3.
1)
{1, 1, 1}
{2, 0, 4}
Returns: 2
No two eels are in front of Rabbit at the same time, so Rabbit can catch at most two eels.
2)
{1}
{1}
Returns: 1
3)
{50, 51, 8, 41, 53, 34, 67, 59, 42, 64, 52, 20, 39, 71, 17, 59, 32, 65, 9, 49, 20, 72, 70}
{40, 52, 32, 0, 61, 55, 59, 42, 55, 61, 55, 23, 35, 22, 11, 22, 52, 65, 5, 28, 56, 6, 15}
Returns: 21
4)
{314, 430, 907, 346, 449, 405, 841, 50, 407, 9, 649, 420, 577, 67, 917, 152, 588, 674, 514, 433, 504, 233, 797, 771, 413, 898, 246, 834, 424, 497, 799, 918, 169, 777, 208, 378, 606, 225, 139, 855, 258, 10, 528, 542, 67, 533, 162, 54, 266, 310}
{363, 533, 470, 417, 490, 735, 729, 564, 251, 726, 650, 761, 707, 134, 541, 542, 82, 61, 467, 552, 132, 58, 107, 761, 555, 801, 367, 656, 418, 561, 373, 539, 582, 198, 603, 805, 275, 184, 100, 292, 242, 585, 385, 769, 283, 102, 748, 268, 789, 192}
Returns: 41
Submissions are judged against all 118 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EelAndRabbit with a public method int getmax(vector<int> l, vector<int> t) · 118 test cases · 2 s / 256 MB per case