God! Save me#1575

God! Save me (Editoryal)

Let $P$ denote the expected time to escape the room to a safe place. This time is expressed as follows:

P = i = 1 \sum n p_{i} \cdot t_{i},

P = \sum_{i=1}^n p_i \cdot t_i,

where $t_{i}$ t_i is the time to reach a safe place if the $i$ -th door is chosen. It is clear that $t_{i} = x_{i}$ t_i = x_i if $x_{i} > 0$ x_i > 0. If $x_{i} < 0$ x_i < 0, then to escape, one must first spend time $- x_{i}$ -x_i to return to the room, and then spend time $P$ for another attempt to exit. Thus, in this case, $t_{i} = - x_{i} + P$ t_i = -x_i + P.

As a result, we obtain a linear equation in terms of $P$ . This equation can be constructed and solved in $O (n)$ time, where $n$ is the number of doors.

Example

Let’s consider the first test. Create an equation:

P = 0.33 * 2 + 0.33 * (3 + P) + 0.34 * (5 + P),

P = 0.33 * 2 + 0.33 * (3 + P) + 0.34 * (5 + P),

where from $0.33 \cdot P = 3.35$ 0.33 \cdot P = 3.35 or $P = 10.151515$ P = 10.151515.

Algorithm implementation

We'll solve the linear equation as follows. All terms containing the multiplier $P$ will be moved to the left side, and their coefficients will be stored in the variable $l e f t$ . All constants will be collected on the right side and stored in the variable $r i g h t$ . Initially, set $l e f t = 1$ left = 1 and $r i g h t = 0$ right = 0.

Read $n$ pairs of numbers $x$ and $p$ .

If $x > 0$ x > 0, then increase the right side of the equation by $x \cdot p$ x \cdot p.
If $x < 0$ x < 0, a term $p \cdot (- x + P)$ p \cdot (-x + P) will appear on the right side of the equation. In this case, we should add $p \cdot (- x)$ p \cdot (-x) to the right side and subtract $p$ from the left side.

left = 1.0; right = 0.0;
scanf("%d",&n);
for(j = 0; j < n; j++)
{
  scanf("%lf %lf",&x, &p);
  if (x < 0.0)
  {
    left -= p;
    right += p * (-x);
  } else
      right += x * p;
}

C++

We obtained the equation $l e f t \cdot P = r i g h t$ left \cdot P = right. If $l e f t = 0$ left = 0, then it is impossible to escape from the room (there is no door leading to a safe place). Otherwise, the sought time can be calculated as $P = r i g h t / l e f t$ P = right / left.

if (left > 0.0)
{
  res = right / left;

Print the answer. The variable $i$ corresponds to the test number.

  printf("Case %d: %.2lf\n",i,res);
} else
  printf("Case %d: God! Save me\n",i);