Statistics

Problem Statement for "PulleyTautLine"

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.

Definition

Class:
PulleyTautLine
Method:
getLength
Parameters:
int, int, int, long
Returns:
double
Method signature:
double getLength(int d, int r, int n, long k)
(be sure your method is public)

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

  1. 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.

  2. 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.

  3. 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.

  4. 100

    30

    2

    3

    Returns: 327.67946605191

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

  5. 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.  

  6. 987564321

    123

    3

    123456789987654321

    Returns: 4.299887159886938E9

  7. 1000000000

    499999999

    50

    1000000000000000000

    Returns: 6.981316870248074E10

  8. 3

    1

    1

    1

    Returns: 6.336528068400624

    min answer

  9. 1000000000

    499999999

    3

    1000000000000000000

    Returns: 8.079989149920386E10

    max answer?

  10. 32057107

    16028553

    1

    86

    Returns: 4.302145085126367E9

  11. 998139269

    499069634

    1

    999999999999790705

    Returns: 1.5678734958038187E27

  12. 115195119

    57597559

    1

    1000000000000000000

    Returns: 1.809480682191047E26

  13. 5

    2

    2

    10

    Returns: 30.086770260547254

  14. 999999993

    499999996

    2

    65761038

    Returns: 4.895476104534259E10

  15. 29320203

    14660101

    2

    1000000000000000000

    Returns: 3.2776061287131424E9

  16. 999963951

    499981975

    3

    1

    Returns: 4.2554961707317533E9

  17. 588623499

    294311749

    3

    23584184

    Returns: 2.032515965906144E10

  18. 69

    34

    3

    1000000000000000000

    Returns: 5508.832608670127

  19. 999999801

    499999900

    5

    607

    Returns: 1.310962859994841E10

  20. 3314121

    1657060

    4

    999999999992614648

    Returns: 2.3513794833152306E8

  21. 5626471

    2813235

    5

    1000000000000000000

    Returns: 3.726858418932302E8

  22. 317

    158

    10

    18

    Returns: 3746.9428304719095

  23. 48545413

    24272706

    6

    17149806

    Returns: 1.3643787893032594E9

  24. 999640579

    499820289

    7

    1000000000000000000

    Returns: 6.221557706385803E10

  25. 868298885

    434149442

    16

    1

    Returns: 1.4983061292491173E10

  26. 999999833

    499999916

    17

    4

    Returns: 1.8826442763851524E10

  27. 83

    41

    11

    1000000000000000000

    Returns: 4910.99509552505

  28. 998644813

    499322406

    23

    993

    Returns: 2.5932847010040222E10

  29. 999998741

    499999370

    23

    511612

    Returns: 2.8251188290911385E10

  30. 999999993

    499999996

    28

    1000000000000000000

    Returns: 6.095476096135443E10

  31. 822671663

    411335831

    44

    26

    Returns: 3.770011846403261E10

  32. 999999957

    499999978

    41

    999999999952732983

    Returns: 6.538396225127026E10

  33. 45

    22

    48

    1000000000000000000

    Returns: 3067.280596032556

  34. 147328447

    73664223

    50

    2

    Returns: 7.551415252540619E9

  35. 998976349

    499488174

    50

    585407

    Returns: 5.405424183066228E10

  36. 5225

    2612

    50

    1000000000000000000

    Returns: 364738.96055232536

  37. 132

    28

    1

    521

    Returns: 46011.5510074728

  38. 1000000000

    499500044

    1

    8768

    Returns: 1.3758087338127293E13

  39. 989615955

    492839938

    1

    1000000000000000000

    Returns: 1.5483023286164491E27

  40. 999989262

    279024477

    2

    99

    Returns: 8.905030357746284E9

  41. 999999839

    499999595

    2

    3466754

    Returns: 4.124234405911841E10

  42. 999999502

    499998187

    2

    1000000000000000000

    Returns: 1.1178624280265579E11

  43. 999830414

    499909508

    3

    189

    Returns: 1.2536630968371727E10

  44. 999999994

    494075633

    3

    999999999999890597

    Returns: 8.001166502631393E10

  45. 999999994

    499997197

    3

    1000000000000000000

    Returns: 8.079951015806079E10

  46. 999998198

    496251075

    5

    6

    Returns: 6.811362248571842E9

  47. 999996929

    499941344

    4

    152569

    Returns: 2.2961690326197372E10

  48. 999903486

    463857326

    4

    1000000000000000000

    Returns: 6.735003110917125E10

  49. 999999992

    497969154

    7

    666

    Returns: 1.3076341093908882E10

  50. 999999756

    494257058

    7

    9

    Returns: 8.803587520128536E9

  51. 999999995

    499999798

    6

    1000000000000000000

    Returns: 6.3808724358713394E10

  52. 999999999

    499605229

    12

    7

    Returns: 1.382481338243871E10

  53. 999965657

    483155134

    13

    263149536

    Returns: 3.0487438332894836E10

  54. 999992813

    499475563

    16

    1000000000000000000

    Returns: 5.9207325014128265E10

  55. 999999457

    499823319

    22

    309

    Returns: 2.439594837234355E10

  56. 999999886

    416763272

    27

    103269352

    Returns: 3.3410760932986084E10

  57. 999876383

    137023964

    28

    1000000000000000000

    Returns: 3.917925790655844E10

  58. 999486910

    494755350

    46

    45

    Returns: 4.77819813842719E10

  59. 1000000000

    499999998

    41

    4

    Returns: 4.282644590158484E10

  60. 999999906

    499999051

    41

    1000000000000000000

    Returns: 6.5383892876708664E10

  61. 999999999

    499999996

    50

    885

    Returns: 5.239724215870473E10

  62. 999999996

    498864785

    50

    125516649

    Returns: 5.5225785763158035E10

  63. 3498

    341

    50

    1000000000000000000

    Returns: 184450.5313466753

  64. 993547240

    5321838

    1

    898

    Returns: 1.6967389245267511E10

  65. 15006

    37

    1

    3

    Returns: 30244.56908658646

  66. 999758203

    22259800

    1

    1000000000000000000

    Returns: 6.993122415037808E25

  67. 999995640

    16519142

    2

    636

    Returns: 4.764737924575586E9

  68. 10144

    141

    2

    999999999999999923

    Returns: 200907.6620065879

  69. 999237503

    8896002

    2

    1000000000000000000

    Returns: 1.7518789111213776E10

  70. 40105953

    104504

    3

    1

    Returns: 1.6042408430601388E8

  71. 794002869

    12335791

    3

    59

    Returns: 3.3316025863486214E9

  72. 64

    3

    3

    1000000000000000000

    Returns: 1662.7673998813893

  73. 999999653

    83331394

    4

    11

    Returns: 5.034787746982868E9

  74. 999999948

    5798809

    4

    999999999999999999

    Returns: 1.4712612057412968E10

  75. 34481

    245

    5

    1000000000000000000

    Returns: 524630.0197567008

  76. 48884618

    1638906

    6

    501

    Returns: 3.629523104921808E8

  77. 998343518

    33475885

    9

    999999999999999004

    Returns: 2.2300395368223328E10

  78. 999999987

    14505394

    6

    1000000000000000000

    Returns: 1.7923037005063553E10

  79. 362676

    8111

    20

    1000

    Returns: 7617465.967791431

  80. 13014

    145

    20

    8680

    Returns: 273308.54066226433

  81. 999999988

    61954966

    19

    1000000000000000000

    Returns: 2.907227458904786E10

  82. 13211

    810

    28

    163

    Returns: 383367.581430317

  83. 3348

    68

    23

    999999999999998923

    Returns: 88071.62624787266

  84. 26766

    1849

    26

    1000000000000000000

    Returns: 888270.854114241

  85. 978860697

    3423170

    43

    1000

    Returns: 4.306993052398099E10

  86. 999330197

    18544886

    42

    999999999999999999

    Returns: 4.35644728851539E10

  87. 985039461

    3731183

    41

    1000000000000000000

    Returns: 4.148939886262584E10

  88. 999999999

    1863536

    50

    995

    Returns: 5.100001731284921E10

  89. 2024184

    8567

    50

    999999999999986370

    Returns: 1.0334296179874367E8

  90. 209486516

    9610174

    50

    1000000000000000000

    Returns: 1.0827959412614033E10

  91. 999999995

    23984

    1

    999

    Returns: 2.0751972528625224E9

  92. 701115699

    64816

    1

    999999999999999992

    Returns: 2.0362546943507744E23

  93. 160746749

    1674

    1

    1000000000000000000

    Returns: 5.259026102109635E21

  94. 998286153

    7957

    2

    4

    Returns: 2.9948584591902676E9

  95. 48017875

    38911

    2

    2949163

    Returns: 2.506023886664884E8

  96. 949244168

    96272

    2

    1000000000000000000

    Returns: 7.549631869394976E9

  97. 999849822

    53189

    3

    31

    Returns: 3.999733498490777E9

  98. 999707122

    43692

    3

    41368

    Returns: 4.007064241701889E9

  99. 999999937

    1196

    3

    1000000000000000000

    Returns: 6.033733063741631E9

  100. 1302170

    6

    4

    957

    Returns: 6511000.796585603

  101. 961867522

    14194

    5

    196

    Returns: 5.771383499273956E9

  102. 999996567

    142484

    5

    1000000000000000000

    Returns: 8.457447152894798E9

  103. 999999972

    1320

    7

    1

    Returns: 7.999999776001741E9

  104. 830497

    1

    9

    133

    Returns: 8304970.0000084285

  105. 999967564

    210464

    10

    1000000000000000000

    Returns: 1.1182132637792446E10

  106. 21455230

    1463

    19

    979

    Returns: 4.2910460069831836E8

  107. 999996308

    63293

    12

    999999999999999877

    Returns: 1.303097120857066E10

  108. 999999158

    48185

    18

    1000000000000000000

    Returns: 1.90087639493509E10

  109. 999603038

    247681

    32

    5

    Returns: 3.2986900438110718E10

  110. 999999835

    227441

    26

    999999999680016265

    Returns: 2.7020003593527756E10

  111. 6390

    1

    28

    1000000000000000000

    Returns: 185385.40276202734

  112. 999999999

    100806

    49

    54

    Returns: 4.999999998048555E10

  113. 999999914

    44929

    43

    2

    Returns: 4.3999996218018616E10

  114. 999999987

    3391

    45

    1000000000000000000

    Returns: 4.600008462752797E10

  115. 22186

    2

    50

    78

    Returns: 1131486.0005408814

  116. 96457381

    2682

    50

    22011953

    Returns: 4.91932643196945E9

  117. 999730450

    66683

    50

    1000000000000000000

    Returns: 5.0987091149026215E10

  118. 999999995

    13

    1

    999

    Returns: 2.0000407490230877E9

  119. 984095951

    9

    1

    999999999999999999

    Returns: 2.827433388427633E19

  120. 999999999

    207

    1

    1000000000000000000

    Returns: 6.503096792950871E20

  121. 999999910

    4

    2

    978

    Returns: 3.000000257787566E9

  122. 921114799

    26

    2

    1

    Returns: 2.763344397000001E9

  123. 999999968

    227

    2

    1000000000000000000

    Returns: 5.049912615850475E9

  124. 999996382

    865

    3

    951

    Returns: 4.000023572690776E9

  125. 999999979

    2

    3

    3375

    Returns: 4.0000000667964478E9

  126. 185903186

    2

    3

    1000000000000000000

    Returns: 7.550300331190116E8

  127. 999998033

    15

    4

    182

    Returns: 4.99999035349556E9

  128. 999996208

    29

    5

    999999999999941423

    Returns: 6.000921654733971E9

  129. 999999996

    615

    5

    1000000000000000000

    Returns: 6.020027911911865E9

  130. 999999994

    1

    8

    1

    Returns: 8.999999946E9

  131. 999992018

    5

    9

    49461193

    Returns: 9.999920525575191E9

  132. 999999998

    367

    6

    1000000000000000000

    Returns: 7.003445043938229E9

  133. 999999971

    93

    20

    975

    Returns: 2.099999939100006E10

  134. 321039074

    318

    17

    451

    Returns: 5.778703332002205E9

  135. 82850716

    2

    15

    1000000000000000000

    Returns: 1.3256120089203076E9

  136. 999999999

    505

    22

    2

    Returns: 2.299999997700025E10

  137. 999999999

    4

    33

    999999999999999999

    Returns: 3.400000019219467E10

  138. 204541037

    17

    24

    1000000000000000000

    Returns: 5.113527634026447E9

  139. 999970138

    386

    41

    2

    Returns: 4.199874579600015E10

  140. 33837252

    1

    42

    1000000000000000000

    Returns: 1.4550018674159274E9

  141. 999999999

    846

    45

    1000000000000000000

    Returns: 4.600002121632413E10

  142. 999999993

    391

    50

    999

    Returns: 5.099999964300076E10

  143. 923359356

    1

    50

    11

    Returns: 4.7091327156E10

  144. 101046099

    29

    50

    1000000000000000000

    Returns: 5.15335141342519E9

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: