Задача: Обновление базы данных

Для задач машинного обучения используется кластер из серверов. Кластер организован в виде бинарного дерева: центральный сервер является корнем дерева и имеет уровень \(0\). Каждый сервер уровня \(i\) для \(i\) от \(0\) до \(k-1\) соединен с двумя дочерними серверами уровня \(i+1\). Сервера на уровне \(k\) — рабочие, у них нет дочерних серверов.

Обновление базы данных поступает на центральный сервер и далее распространяется по остальным серверам. Каждый сервер, получив обновление, передает его далее своим дочерним серверам.

Из-за высокой нагрузки передача информации между серверами не всегда происходит успешно. Известно, что вероятность того, что обновление будет успешно передано от сервера к его дочернему серверу, составляет \(0.9\).

Необходимо посчитать среднее число рабочих серверов, которые получат обновление.

Например, если \(k =1\), то есть два рабочих сервера, непосредственно являющиеся дочерними для центрального.

• с вероятностью \(0.9^2\) оба сервера получат обновление;

• с вероятностью \(0.9\cdot 0.1\) первый рабочий сервер получит обновление, а второй — нет;

• с вероятностью \(0.1\cdot 0.9\) первый рабочий сервер не получит обновление, а второй — получит;

• с вероятностью \(0.1^2\) оба сервера не получат обновление.

Среднее число серверов, которые получат обновление, равно \[2\cdot 0.9^2+ 1\cdot 0.9\cdot 0.1+ 1\cdot 0.1\cdot 0.9+ 0\cdot 0.1^2=1.62+0.09+0.09+0=1.8.\]

В этой задаче вам необходимо предоставить на проверку файл с расширением <<.txt>>. Вы можете самостоятельно вручную создать этот файл или написать программу, которая его создаст.

В файле должны быть одна или две строки.

Первая строка должна содержать среднее количество рабочих серверов, которые получат обновление, если \(k = 2\). Если это значение верно, вы получите 50 баллов.

Вторая строка может содержать среднее количество рабочих серверов, которые получат обновление, если \(k = 20\). Если это значение верно, вы получите еще 50 баллов.

Ваш ответ будет засчитан, если он имеет абсолютную или относительную погрешность не больше \(10^{-6}\).

Пример выходного файла ниже содержит корректное форматирование, но некорректные значения.

Ваш ответ: