Editorial

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

where $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$ if $x_i>0$. If $x_i<0$, then to escape, one must first spend time $-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$.

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:

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

Algorithm realization

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 $left$. All constants will be collected on the right side and stored in the variable $right$. Initially, set $left=1$ and $right=0$.

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

• If $x>0$, then increase the right side of the equation by $x\cdot p$.

• If $x<0$, a term $p\cdot (-x+P)$ will appear on the right side of the equation. In this case, we should add $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;
}

We obtained the equation $left\cdot P=right$. If $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=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);