CtuRobots
SRM 647 · 2014-12-30 · by lg5293
Problem Statement
Once Ctu purchases some robots, he will number them sequentially, starting from 1. Note that he may number them in any order - he is not required to preserve the order in which the robots' parameters are given in cost and cap.
The robots are going to travel along a straight line. They will all start at the position 0 on the line. Ctu wants to send a robot as far as possible in the positive direction. Precise rules of robot movement are given below.
- The robots' movement is continuous. They are able to travel arbitrary positive real distances.
- Moving 1 unit of distance consumes 1 unit of fuel.
- The robots will initially all travel together in the positive direction. One by one, in the order given by their numbers, the robots will then turn back. Multiple robots with consecutive numbers may turn back at the same position.
- Each robot must return back to position 0.
- As a robot turns back, it can donate any amount of fuel to the next robot. (I.e., for each valid k, robot k may donate some of its fuel to robot k+1. Note that after the donation robot k must still have enough fuel to get back to position 0.)
- The amount of fuel a robot carries can never exceed the initial capacity of its fuel tank.
Given that Ctu buys the optimal subset of robots he can afford, and given that he then numbers and programs them optimally, compute and return the largest position that can be reached by one of Ctu's robots.
Notes
- Your return value must have an absolute or relative error smaller than or equal to 1e-6
Constraints
- B will be between 1 and 10,000, inclusive.
- cost will have between 1 and 500 elements, inclusive.
- cap will have exactly the same number of elements as cost.
- Each element of cost will be between 0 and B, inclusive.
- Each element of cap will be between 0 and 1,000,000,000, inclusive.
100
{50,25}
{1,1}
Returns: 0.6666666666666666
In this case, Ctu has a budget of 100 dollars. He can buy both robots for 50+25 = 75 dollars. One of the robots will get the number 1 and the other will get the number 2. If they cooperate, one of these robots can reach the position 2/3 = 0.666666667. Here's how an optimal program looks like: Both robots travel together to the position 1/3. At this moment, each of them has 2/3 of a unit of fuel in its fuel tank. Robot 1 donates 1/3 of a unit of fuel to robot 2 and turns back. Robot 2 now has a full fuel tank again. It continues to the position 2/3. There it turns back and returns to position 0.
25
{23,5,8,20,15}
{108,30,42,100,94}
Returns: 55.0
1382
{0,0,0,1000,1000,0,1000,0}
{2039,4819,5923,1577,8749,9182,3652,4918}
Returns: 6503.238683127572
209
{185,130,109,1,45,117,127,13,2,37,6,1,2}
{93,5,278,4,20,54,93,213,103,5,225,32,5}
Returns: 190.48376771833563
9956
{3229,736,1325,2680,410,1227,1378,499,1525,1722,1262,2080,2581,1505,1019,
480,3155,836,2697,616,136,2032,2345,3154,1953,1654,344,3079,1426,199,2857,
1714,2952,996,1567,2674,2054,2110,949,2412,2148,1016,234,1932,1554,1943,
1625,1266,258,2924,49,1693,3140,309,557,12,2760,227,2497,330,646,1935,3032,
2671,2433,164,1472,3080,717,221,2483,1309,1174,12,917,2335,3086,148,64,189,
2628,1660,2983,109,1920,2470}
{934850,214,15807606,2426,176520,1900009,1184867,40550,1774843,2953,77834310,
7276,3139890,695,213862217,13,193864,189,557664,1206555,85133,381662,4887,
115027,2186890,218075,1,2024,9,95244962,7,906,3485642,52962078,58645759,785706,
303,18,189,819600,17528041,11616471,92719012,82351,12752,634,26122233,215485,
58,5506810,101874,130429471,2,1,68966,76303,321766922,463,26,225,207,52,1739,
246841,496,228,4749453,191,79,10560,1414194,7529,13,521935,1,2,11590618,4020,
105,3,28,3,2855,189909573,1,295052}
Returns: 2.1034261053998655E8
Submissions are judged against all 85 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CtuRobots with a public method double maxDist(int B, vector<int> cost, vector<int> cap) · 85 test cases · 2 s / 256 MB per case