Statistics

Problem Statement for "Starport"

Problem Statement

A new starport has just started working. Starting from some moment of time (call it minute 0), a new spaceship arrives at the starport every M minutes. In other words, spaceships arrive at the starport at minutes 0, M, 2*M, 3*M and so on.

Similarly, starting from minute 0 and repeating each N minutes, all arrived spaceships that are still placed at the port are teleported to the shed. If a spaceship arrives at the exact same minute when such a teleportation happens, it will be teleported immediately. Otherwise it will need to wait until the next teleportation happens.

Let the waiting time of a spaceship be the time between its arrival and its teleportation to the shed. Return the average waiting time of a spaceship in minutes. See notes for an exact definition.

Definition

Class:
Starport
Method:
getExpectedTime
Parameters:
int, int
Returns:
double
Method signature:
double getExpectedTime(int N, int M)
(be sure your method is public)

Notes

  • Let W(i) be the waiting time for the spaceship that arrives at minute M * i. The average waiting time can be defined as the limit of (W(0) + W(1) + ... + W(P - 1)) / P when P tends to positive infinity. This limit will always exist.
  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • N and M will each be between 1 and 1,000,000,000, inclusive.

Examples

  1. 4

    2

    Returns: 1.0

    Spaceships arrive at the starport at minutes 0, 2, 4, 6, 8, and so on. Teleportations are done at minutes 0, 4, 8, and so on. The waiting times for the spaceships are, correspondingly, 0, 2, 0, 2, 0, and so on, so the expected waiting time is 1.

  2. 5

    3

    Returns: 2.0

  3. 6

    1

    Returns: 2.5

  4. 12345

    2345

    Returns: 6170.0

  5. 1

    1000000000

    Returns: 0.0

  6. 1000000000

    1

    Returns: 4.999999995E8

  7. 1000000000

    1000000000

    Returns: 0.0

  8. 1000000000

    999999999

    Returns: 4.999999995E8

  9. 999999999

    1000000000

    Returns: 4.99999999E8

  10. 12

    5

    Returns: 5.5

  11. 14

    12

    Returns: 6.0

  12. 6

    7

    Returns: 2.5

  13. 9

    13

    Returns: 4.0

  14. 14

    10

    Returns: 6.0

  15. 2

    14

    Returns: 0.0

  16. 11

    1

    Returns: 5.0

  17. 9

    10

    Returns: 4.0

  18. 4

    13

    Returns: 1.5

  19. 11

    9

    Returns: 5.0

  20. 1

    47

    Returns: 0.0

  21. 1

    53

    Returns: 0.0

  22. 1

    73

    Returns: 0.0

  23. 1

    27

    Returns: 0.0

  24. 96

    1

    Returns: 47.5

  25. 7046131

    1

    Returns: 3523065.0

  26. 8821408

    1

    Returns: 4410703.5

  27. 1

    3862670

    Returns: 0.0

  28. 1

    7357215

    Returns: 0.0

  29. 1184139

    1

    Returns: 592069.0

  30. 100000000

    1000000

    Returns: 4.95E7

  31. 1

    1

    Returns: 0.0

  32. 7

    7

    Returns: 0.0

  33. 536870912

    536870912

    Returns: 0.0

  34. 701408733

    433494437

    Returns: 3.50704366E8

  35. 700776761

    150563401

    Returns: 3.5038838E8

  36. 289801000

    462555205

    Returns: 1.449004975E8

  37. 610548375

    828728634

    Returns: 3.05274186E8

  38. 843858085

    587573580

    Returns: 4.2192904E8

  39. 926721076

    318260246

    Returns: 4.63360537E8

  40. 396643072

    561141801

    Returns: 1.983215355E8

  41. 875126809

    783703811

    Returns: 4.37563404E8

  42. 426219907

    965110942

    Returns: 2.13109953E8

  43. 349927638

    580671298

    Returns: 1.74963818E8

  44. 886918310

    641958573

    Returns: 4.434591545E8

  45. 253770905

    631600262

    Returns: 1.26885452E8

  46. 360396889

    298547569

    Returns: 1.80198444E8

  47. 770993956

    505252854

    Returns: 3.85496977E8

  48. 69946468

    528890679

    Returns: 3.49732335E7

  49. 260001211

    384396188

    Returns: 1.30000605E8

  50. 728057387

    466304827

    Returns: 3.64028693E8

  51. 585210999

    86736168

    Returns: 2.92605498E8

  52. 319828794

    744254367

    Returns: 1.599143955E8

  53. 688734193

    436415944

    Returns: 3.44367096E8

  54. 146682056

    684418574

    Returns: 7.3341027E7

  55. 650381000

    45693000

    Returns: 3.2519E8

  56. 355279000

    928984000

    Returns: 1.77639E8

  57. 668342000

    279221000

    Returns: 3.341705E8

  58. 403710000

    360056000

    Returns: 2.01854E8

  59. 667949000

    969780000

    Returns: 3.33974E8

  60. 438041727

    711722994

    Returns: 2.19018012E8

  61. 511292960

    966272597

    Returns: 2.556455295E8

  62. 574755944

    679156963

    Returns: 2.873770215E8

  63. 508042250

    985006952

    Returns: 2.54019224E8

  64. 271422879

    834149295

    Returns: 1.35691479E8

  65. 194478570

    491301045

    Returns: 9.72346275E7

  66. 873930195

    953921205

    Returns: 4.36963545E8

  67. 195615

    373469400

    Returns: 96255.0

  68. 450762165

    177211665

    Returns: 2.2537953E8

  69. 269063775

    572493690

    Returns: 1.34530335E8

  70. 845619711

    63577962

    Returns: 4.22809794E8

  71. 353871615

    147598647

    Returns: 1.76935746E8

  72. 70467315

    122463105

    Returns: 3.523335E7

  73. 868656627

    827791230

    Returns: 4.34328252E8

  74. 899418435

    996159288

    Returns: 4.49709156E8

  75. 665431613

    17283938

    Returns: 3.28394822E8

  76. 303703482

    751851303

    Returns: 1.499998905E8

  77. 30864175

    713579726

    Returns: 1.4814804E7

  78. 641974840

    990122734

    Returns: 3.19752853E8

  79. 724690829

    240740565

    Returns: 3.61728131E8

  80. 545169920

    894600640

    Returns: 2.7186E8

  81. 142390130

    144146365

    Returns: 7.11275175E7

  82. 542524311

    745550757

    Returns: 2.70926019E8

  83. 654774512

    520522184

    Returns: 3.26209604E8

  84. 816773670

    142995060

    Returns: 4.0833495E8

  85. 721123123

    534535343

    Returns: 3.60561561E8

  86. 20996011

    3

    Returns: 1.0498005E7

  87. 3

    5

    Returns: 1.0

  88. 997007078

    997007079

    Returns: 4.985035385E8

  89. 1000000000

    3

    Returns: 4.999999995E8

  90. 999999937

    999999929

    Returns: 4.99999968E8

  91. 999999929

    999999937

    Returns: 4.99999964E8

  92. 1000000000

    999999929

    Returns: 4.999999995E8

  93. 100000009

    100000007

    Returns: 5.0000004E7

  94. 999999999

    999999998

    Returns: 4.99999999E8

  95. 646119602

    178503576

    Returns: 3.230598E8

  96. 999999998

    999999999

    Returns: 4.999999985E8

  97. 999999993

    999999997

    Returns: 4.99999996E8

  98. 999999997

    1

    Returns: 4.99999998E8

  99. 9875475

    9854753

    Returns: 4937737.0

  100. 982451653

    982451707

    Returns: 4.91225826E8

  101. 100000000

    1210985

    Returns: 4.99999975E7

  102. 100000007

    100000009

    Returns: 5.0000003E7

  103. 100000007

    1000000000

    Returns: 5.0000003E7

  104. 6

    8

    Returns: 2.0

  105. 856712345

    6

    Returns: 4.28356172E8

  106. 99999989

    13

    Returns: 4.9999994E7

  107. 99999989

    94418953

    Returns: 4.9999994E7

  108. 1000000000

    1000007

    Returns: 4.999999995E8

  109. 982451653

    15485863

    Returns: 4.91225826E8

  110. 536870912

    199999994

    Returns: 2.68435455E8

  111. 999617293

    999617279

    Returns: 4.99808646E8

  112. 37637323

    524287

    Returns: 1.8818661E7

  113. 999999997

    1000000000

    Returns: 4.99999998E8

  114. 100000000

    99999999

    Returns: 4.99999995E7

  115. 987989982

    7345284

    Returns: 4.93994988E8

  116. 1000000000

    999999997

    Returns: 4.999999995E8

  117. 866988874

    100712442

    Returns: 4.33494436E8

  118. 999999893

    999999937

    Returns: 4.99999946E8

  119. 999888733

    1000000000

    Returns: 4.99944366E8

  120. 999999999

    889329422

    Returns: 4.99999999E8

  121. 100000000

    1

    Returns: 4.99999995E7

  122. 999999992

    999999993

    Returns: 4.999999955E8

  123. 999999998

    999999996

    Returns: 4.99999998E8

  124. 20996011

    24036583

    Returns: 1.0498005E7

  125. 311

    1000000000

    Returns: 155.0

  126. 100000001

    3

    Returns: 5.0E7

  127. 1000000000

    4456332

    Returns: 4.99999998E8

  128. 999999997

    999999991

    Returns: 4.99999998E8

  129. 999999995

    999999997

    Returns: 4.99999997E8

  130. 999999937

    800000011

    Returns: 4.99999968E8

  131. 1

    999999999

    Returns: 0.0

  132. 433434

    3232233

    Returns: 216715.5

  133. 1000000000

    999999991

    Returns: 4.999999995E8

  134. 1000000000

    2345

    Returns: 4.999999975E8

  135. 100000000

    999999999

    Returns: 4.99999995E7

  136. 999000011

    999000029

    Returns: 4.99500005E8

  137. 10000000

    9999999

    Returns: 4999999.5

  138. 125467865

    875556644

    Returns: 6.2733932E7

  139. 65536

    65536

    Returns: 0.0

  140. 3

    4

    Returns: 1.0

  141. 100000000

    9999999

    Returns: 4.99999995E7

  142. 999999997

    999999998

    Returns: 4.99999998E8

  143. 99999999

    123

    Returns: 4.9999998E7

  144. 999999999

    777777778

    Returns: 4.99999999E8

  145. 536870912

    387420489

    Returns: 2.684354555E8

  146. 1233432

    3242345

    Returns: 616715.5

  147. 3

    7

    Returns: 1.0

  148. 21474836

    123123213

    Returns: 1.07374175E7

  149. 900000009

    12242

    Returns: 4.50000004E8

  150. 1000000000

    499999999

    Returns: 4.999999995E8

  151. 999999999

    999999997

    Returns: 4.99999999E8

  152. 500000041

    500000003

    Returns: 2.5000002E8

  153. 999999999

    1

    Returns: 4.99999999E8

  154. 999992999

    992999999

    Returns: 4.99996499E8

  155. 999999996

    999999997

    Returns: 4.999999975E8

  156. 999999991

    999999989

    Returns: 4.99999995E8

  157. 999999999

    99999999

    Returns: 4.99999995E8

  158. 500000000

    7

    Returns: 2.499999995E8

  159. 1000000000

    999999998

    Returns: 4.99999999E8

  160. 2

    4

    Returns: 0.0

  161. 999999937

    999999893

    Returns: 4.99999968E8

  162. 999999151

    1000000000

    Returns: 4.99999575E8

  163. 10000007

    100000007

    Returns: 5000003.0

  164. 19587619

    19587671

    Returns: 9793809.0

  165. 999100211

    999100213

    Returns: 4.99550105E8

  166. 200000000

    300000000

    Returns: 5.0E7

  167. 10000000

    10000001

    Returns: 4999999.5

  168. 12

    8

    Returns: 4.0

  169. 7

    13

    Returns: 3.0

  170. 999999997

    887657890

    Returns: 4.99999998E8

  171. 999999997

    999999993

    Returns: 4.99999998E8

  172. 999999999

    979593913

    Returns: 4.99999999E8

  173. 999999937

    99999989

    Returns: 4.99999968E8

  174. 1000000000

    9

    Returns: 4.999999995E8

  175. 500000000

    1000000000

    Returns: 0.0

  176. 987654321

    1000000000

    Returns: 4.9382716E8

  177. 104729

    104723

    Returns: 52364.0

  178. 9999999

    1000000000

    Returns: 4999999.0

  179. 99999999

    99999998

    Returns: 4.9999999E7

  180. 99999999

    1000000000

    Returns: 4.9999999E7

  181. 1000000000

    999999971

    Returns: 4.999999995E8

  182. 99999997

    1000000000

    Returns: 4.9999998E7

  183. 999009019

    999008537

    Returns: 4.99504509E8

  184. 536870911

    536870913

    Returns: 2.68435455E8

  185. 100613

    100621

    Returns: 50306.0

  186. 1000000000

    99999999

    Returns: 4.999999995E8

  187. 999999997

    2

    Returns: 4.99999998E8

  188. 1

    999999997

    Returns: 0.0

  189. 1000000000

    999999937

    Returns: 4.999999995E8

  190. 2345

    1000000000

    Returns: 1170.0

  191. 99998888

    7778888

    Returns: 4.999944E7

  192. 4

    6

    Returns: 1.0

  193. 100000000

    99999990

    Returns: 4.9999995E7

  194. 999999999

    2

    Returns: 4.99999999E8

  195. 999999992

    999999997

    Returns: 4.999999955E8

  196. 99999999

    99999991

    Returns: 4.9999999E7

  197. 4

    4

    Returns: 0.0

  198. 1000000000

    2

    Returns: 4.99999999E8

  199. 123456789

    100000000

    Returns: 6.1728394E7

  200. 999999999

    45235621

    Returns: 4.99999999E8

  201. 1000000000

    500000001

    Returns: 4.999999995E8

  202. 2

    1000

    Returns: 0.0

  203. 12365656

    234

    Returns: 6182827.0

  204. 1000000000

    99

    Returns: 4.999999995E8

  205. 2

    6

    Returns: 0.0

  206. 6

    4

    Returns: 2.0

  207. 999008537

    999009019

    Returns: 4.99504268E8

  208. 199999997

    199999991

    Returns: 9.9999998E7

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: