Разбор

Обозначим через $P$ ожидаемое время, через которое можно выбраться из комнаты в безопасное место. Тогда это время выражается следующим образом:

где $t_i$ — время выхода в безопасное место, если выбрать $i$ - ую дверь. Очевидно, что $t_i=x_i$, если $x_i>0$. Если $x_i<0$, то для того чтобы выбраться, нужно сначала потратить время $-x_i$ на возвращение в комнату, а затам время $P$ на повторную попытку выхода. Таким образом, в этом случае $t_i=-x_i+P$.

В результате получаем линейное уравнение относительно $P$. Построить и решить это уравнение можно за время $O(n)$, где $n$ — количество дверей.

Пример

Рассмотрим первый тест. Составим уравнение:

откуда $0.33\cdot P=3.35$ или $P=10.151515$.

Реализация алгоритма

Решение линейного уравнения будем проводить следующим образом. Все слагаемые, содержащие множитель $P$, перенесем влево, а их коэффициенты будем хранить в переменной $left$. Все константы соберем справа и сохраним в переменной $right$. Изначально установим $left=1$ и $right=0$.

Читаем $n$ пар чисел $x$ и $p$.

• Если $x>0$, то увеличиваем правую часть уравнения на величину $x\cdot p$.

• Если $x<0$, то в правой части уравнения появится слагаемое $p\cdot (-x+P)$. В этом случае следует прибавить к правой части величину $p\cdot (-x)$, а из левой вычесть $p$.

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;
}

Получили уравнение $left\cdot P=right$. Если $left=0$, то выбраться из комнаты невозможно (не существует двери, ведущей в безопасное место). В противном случае искомое время можно вычислить как $P=right/left$.

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

Выводим ответ. Переменной $i$ соответствует номер теста.

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