Боже! Врятуй мене#1575

Боже! Врятуй мене (Розбір)

Позначимо через $P$ очікуваний час, через який можна вибратися з кімнати в безпечне місце. Тоді цей час виражається наступним чином:

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

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

де $t_{i}$ t_i — час виходу в безпечне місце, якщо вибрати $i$ -ті двері. Очевидно, що $t_{i} = x_{i}$ t_i = x_i, якщо $x_{i} > 0$ x_i > 0. Якщо $x_{i} < 0$ x_i < 0, то для того щоб вибратися, потрібно спочатку витратити час $- x_{i}$ -x_i на повернення в кімнату, а потім час $P$ на повторну спробу виходу. Таким чином, у цьому випадку $t_{i} = - x_{i} + P$ t_i = -x_i + P.

У результаті отримуємо лінійне рівняння відносно $P$ . Побудувати і розв’язати це рівняння можна за час $O (n)$ , де $n$ — кількість дверей.

Приклад

Розглянемо перший тест. Складемо рівняння:

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

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

звідки $0.33 \cdot P = 3.35$ 0.33 \cdot P = 3.35 або $P = 10.151515$ P = 10.151515.

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

Рішення лінійного рівняння будемо проводити наступним чином. Всі доданки, що містять множник $P$ , перенесемо вліво, а їх коефіцієнти будемо зберігати в змінній $l e f t$ . Всі константи зберемо праворуч і збережемо в змінній $r i g h t$ . Спочатку встановимо $l e f t = 1$ left = 1 і $r i g h t = 0$ right = 0.

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

Якщо $x > 0$ x > 0, то збільшуємо праву частину рівняння на величину $x \cdot p$ x \cdot p.
Якщо $x < 0$ x < 0, то в правій частині рівняння з’явиться доданок $p \cdot (- x + P)$ p \cdot (-x + P). У цьому випадку слід додати до правої частини величину $p \cdot (- x)$ 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;
}

C++

Отримали рівняння $l e f t \cdot P = r i g h t$ left \cdot P = right. Якщо $l e f t = 0$ left = 0, то вибратися з кімнати неможливо (не існує дверей, що ведуть у безпечне місце). В іншому випадку шуканий час можна обчислити як $P = r i g h t / l e f t$ 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);