Bubbles in liquid

The formulas that describe the vertical speed of a bubble of gas inside
a liquid are extremely difficult. Thus, in this problem, we will settle
for big simplifications.

0.75 We have n bubbles at several depths. All bubbles are on the same
vertical line, separated from one another. Each bubble i is a perfect
sphere with radius r_(i), and its center is at depth d_(i). Assume that
the speed of each bubble is c ⋅ r_(i)², where c is a given constant.
When two bubbles meet (i.e., when they just begin to touch), they
instantly merge into a single bubble. The volume of the new bubble is
the sum of the volumes of the two previous bubbles. The depth of the
center of the new bubble is the center of mass of the two previous
bubbles. When a bubble touches the surface of the water, it disappears.
Your task is to compute the time it takes for all the bubbles to
disappear.

0.19 [image]

For instance, consider the first case of the sample input, with a bubble
with radius 1 at depth 11, and a bubble with radius 2 at depth 20 (see
the first column below). Since c = 2, the speed of the smaller bubble is
2 ⋅ 1² = 2, and the speed of the larger bubble is 2 ⋅ 2² = 8. After
exactly one unit of time, the bubbles touch each other (second column),
and immediately merge into a single, larger bubble (third column). With
some simple computations, we find that the new bubble has radius
 ≃ 2.0801, and its depth is  ≃ 11.6667. After about 1.1078 more units of
time, this bubble reaches the surface of the liquid (fourth column) and
disappears.

[image]

You can assume that these situations will never happen:

- Two or more consecutive bubbles with the same (or very similar) radii.

- Three or more consecutive bubbles that would disappear at the same (or
  very similar) moments, with the first touching the second, the second
  touching the third, and so on.

Input

Input consists of several cases, each with n, the real constant c, and n
pairs of real numbers d_(i) r_(i) defining each bubble. Assume
1 ≤ n ≤ 10⁵, c > 0, and that the bubbles are initially separated and
strictly inside the liquid.

Output

For each case, print with 4 digits after the decimal point the time for
all the bubbles to disappear. The input cases have no precision issues.

Problem information

Author: Salvador Roura
Event: Vint-i-quatrè Concurs de Programació de la UPC - Final
Date: 2026-10-07

Generation: 2026-10-07T12:26:35.487Z

© Jutge.org, 2006–2026.
https://jutge.org
