Задача

Автобус с $n$ пассажирами открывает двери на автобусной остановке. В точности половина пассажиров плюс полпассажира выходит. На следующей остановке снова половина пассажиров плюс полпассажира выходит из автобуса. Так продолжается $k$ остановок. Зная, что на последней остановке автобус стал пустым, и никто не пострадал во время поездки, определите начальное количество людей $n$ в автобусе.

Входные данные

Первая строка содержит количество тестов  $t$. Каждый тест содержит в отдельной строке количество остановок $k(1 \leq k \leq 30).$

Выходные данные

Для каждого теста вывести в отдельной строке начальное количество пассажиров.

Тесты

Код

Решение

Число пассажиров обязано быть нечётным, так как если бы оно было чётным, то какого-то пассажира пришлось бы резать пополам, что противоречит условию.
На последней остановке должен выйти всего один пассажир, потому что обязательно из автобуса выйдет пол пассажира и половина от всех едущих, и при этом автобус опустеет.
Значит:
$$\frac{x}{2} + 0.5 = x$$
$$\frac{x}{2} = x — 0.5$$
$$x = 2x — 1$$
$$x = 1,$$
где $x$ — число пассажиров в автобусе.
Тогда на предпоследней остановке было:
$$x = x_0 + \frac{x}{2} + 0.5$$
$$\frac{x}{2} = x_0 + 0.5$$
$$x = 2(x_0 + 0.5) = 2x_0 + 1,$$
где $x_0$ — число пассажиров оставшихся в автобусе. Значит $x = 3$
И так далее. А значит на $k$-ой остановке перед выходом пассажиров было:
$x = 2\cdot \left(2\cdot\left(2\cdot\left( \cdots 2\cdot\left(0\right) + 1\right) + \ldots +1\right) + 1\right) + 1$ или $x = 2^n \cdot 0 + 2^{n-1} + \ldots + 2 + 1$
Свернём по формуле суммы геометрической прогрессии, где $b = 1$ и $q = 2.$
[latex]S_k = \frac{b\left(q^k -1\right)}{q-1} = 2^{k} — 1.[/latex]

Ссылки

• e-olymp
• ideone

Related Images: