Задача
Автобус с $n$ пассажирами открывает двери на автобусной остановке. В точности половина пассажиров плюс полпассажира выходит. На следующей остановке снова половина пассажиров плюс полпассажира выходит из автобуса. Так продолжается $k$ остановок. Зная, что на последней остановке автобус стал пустым, и никто не пострадал во время поездки, определите начальное количество людей $n$ в автобусе.
Входные данные
Первая строка содержит количество тестов $t$. Каждый тест содержит в отдельной строке количество остановок $k(1 \leq k \leq 30).$
Выходные данные
Для каждого теста вывести в отдельной строке начальное количество пассажиров.
Тесты
| Входные данные | Выходные данные | |
| 1 | 2 1 3 |
1 7 |
| 2 | 3 0 15 12 |
0 32767 4095 |
| 3 | 7 5 8 10 19 4 1 9 |
31 255 1023 524287 15 1 511 |
| 4 | 4 23 17 2 8 |
8388607 131071 3 255 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> using namespace std; int main() { int n; int k; cin >> n; while (n-- > 0) { cin >> k; cout << (1 << k) - 1 << endl; } return 0; } |
Решение
Число пассажиров обязано быть нечётным, так как если бы оно было чётным, то какого-то пассажира пришлось бы резать пополам, что противоречит условию.
На последней остановке должен выйти всего один пассажир, потому что обязательно из автобуса выйдет пол пассажира и половина от всех едущих, и при этом автобус опустеет.
Значит:
$$\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]