PulleyTautLine

SRM 607 · 2013-12-22 · by mystic_tc

SRM 607 · 2013-12-22 · by mystic_tc · Geometry, Math

Show categories

Class Name: PulleyTautLine

Return Type: double

Method Name: getLength

Arg Types: (int, int, int, long long)

Problem Statement

Andrew has an interesting contraption. There are two nails and n pulleys on his table. The nails are points with coordinates (0, 0) and ((n+1)*d, 0). Each pulley is a circle with radius r. The centers of the pulleys are at the points (d, 0), (2*d, 0), ..., and (n*d, 0). The constraints guarantee that no two pulleys overlap.

Andrew wants to connect the two nails using a piece of rope. His only condition is that the rope must be perfectly taut. In other words, there must be no slack anywhere on the rope. (Assume that the width of the rope is negligible and that the length of the rope is not limited.)

Of course, the rope cannot go directly from one nail to the other, because the pulleys are in the way. The rope has to go around them somehow: touching some of them, or even wrapping around them. The rope is even allowed to touch the same point on a pulley arbitrarily many times.

Given these constraints it's easy to see that there are infinitely many ways how to stretch the rope between the two nails. Note that two ways are considered different if the rope follows a different curve, even if the length of the rope is exactly the same in both ways.

Andrew ordered all possible ways according to the length of the rope used. (The order starts with the shortest ways, and ties are broken arbitrarily.) You are given the ints d, r, n (as described above), and a long k. Return the length of the rope used in the k-th (1-based index) way in his ordered list.

Notes

Your return value must have an absolute or a relative error of less than 1e-9.

Constraints

r will be between 1 and 499,999,999, inclusive.
d will be between 2*r+1 and 1,000,000,000, inclusive.
n will be between 1 and 50, inclusive.
k will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.

Examples

100
30
1
1
Returns: 209.06939952431298

Here we are looking for the shortest possible solution. There are two ways to achieve it: start at the left nail, pull the rope above or below the pulley and directly proceed to the right nail.

100
30
1
2
Returns: 209.06939952431298

As there are two ways to achieve the shortest possible solution, the answer here is the same as in previous example.

1000000000
499999999
1
1000000000000000000
Returns: 1.570796323653304E27

One of the solutions with such length is: start at the left nail, pull the rope above the pulley, wrap it 499,999,999,999,999,999 times around the pulley and finish at the right nail.

100
30
2
3
Returns: 327.67946605191

One solution with such length is shown on the picture below.

100
30
2
35
Returns: 734.7850917948947

One solution with such length starts as on the left picture and ends as on the right picture.

3
1
1
1
Returns: 6.336528068400624

min answer

1000000000
499999999
3
1000000000000000000
Returns: 8.079989149920386E10

max answer?

Submissions are judged against all 144 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PulleyTautLine with a public method double getLength(int d, int r, int n, long long k) · 144 test cases · 2 s / 256 MB per case