10777. Боже! Спаси меня

В комнате имеется n дверей. Если Вы откроете дверь с номером i, то либо через x_i часов попадете в безопасное место, либо через x_i часов снова вернетесь в эту же комнату. Вычислить ожидаемое время P (в часах), через которое можно выбраться из комнаты в безопасное место.

Вход. Первая строка содержит количество тестов. Каждый тест содержит следующие данные. Первая строка каждого теста содержит число дверей n (1 < n < 100). Далее следует n строк, каждая из которых содержит числа x_i, 0 < | x_i | < 25 (если x_i положительно, то оно обозначает время, за которое можно попасть в безопасное место; если отрицательно, то | x_i | – это время, через которое Вы снова окажетесь в комнате) и p_i – вероятность открыть i – ую дверь. Сумма всех p_i равна 1.

Выход. Для каждого теста вывести его номер, двоеточие, пробел, а затем фразу “God! Save me”, если выбраться из комнаты невозможно или ожидаемое время P (с двумя десятичными знаками), через которое можно выбраться из комнаты в безопасное место.

Пример входа

2

3

2 0.33

-3 0.33

-5 0.34

3

2 0.34

-3 0.33

-5 0.33

Пример выхода

Case 1: 10.15

Case 2: 9.76

РЕШЕНИЕ

вероятность + математика

Анализ алгоритма

Обозначим через P ожидаемое время, через которое можно выбраться из комнаты в безопасное место. Тогда оно равно

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 – количество дверей.

Пример

Рассмотрим входные данные для первого теста. Составим по ним уравнение:

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

откуда 0.33 * P = 3.35 или P = 10.15.

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

Линейное уравнение будем решать следующим образом. Все слагаемые, в которых встречается множитель P, будем переносить влево, а коэффициент при нем хранить в переменной left. Все слагаемые-константы будем собирать справа, и хранить в переменной right. Изначально left = 1, right = 0. Читаем n пар чисел x и p. Если x > 0, то увеличиваем правую сторону на величину x * p. Если x < 0, то в правой части уравнения появится слагаемое p * (-x + P). И тогда следует прибавить к правой части величину p * (-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 * P = right. Если left = 0, то выбраться из комнаты невозможно (не существует двери, ведущей в безопасное место). Иначе искомое время равно P = right / left.

if (left > 0.0)

{

res = right / left;

printf("Case %d: %.2lf\n",i,res);

} else

printf("Case %d: God! Save me\n",i);

Здесь переменной i соответствует номер теста.