e-olymp 6777. Автобус

Задача

Автобус с $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

Код

Решение

Число пассажиров обязано быть нечётным, так как если бы оно было чётным, то какого-то пассажира пришлось бы резать пополам, что противоречит условию.
На последней остановке должен выйти всего один пассажир, потому что обязательно из автобуса выйдет пол пассажира и половина от всех едущих, и при этом автобус опустеет.
Значит:
$$\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]

Ссылки

8 thoughts on “e-olymp 6777. Автобус

  1. Насколько я понимаю, исходный код должен также присутствовать в отчете. Добавьте, пожалуйста.

    Кроме того, Вы не продемонстрировали, как именно прийти к формуле $2^k-1$, поскольку многие функции «растут как степень двойки», но их значения, тем не менее, не совпадают с $2^k-1$. Например, так ведет себя $2^k$.

  2. В LaTeX’e есть символ стрелки вправо — лучше бы использовать его, я думаю.
    И вместо косой черты тоже лучше использовать горизонтальную дробь.

  3. Нет, вы не исправили. Последнюю дробь желательно в latex [latex]\frac{b\left(q^k-1\right)}{q-1} [/latex] и еще у вас красным подсвечивается \cdot.

    • Вычистил кучу мусора в тексте: div class=»im_history_message_wrap»
      div class=»im_message_outer_wrap hasselect» data-msg-id=»7234″
      div class=»im_message_wrap clearfix»
      div class=»im_content_message_wrap im_message_in»
      div class=»im_message_body»
      Можете не работать в визуальном режиме? Или научитесь переходить потом в текстовый и удалять все, что не понятно.

Добавить комментарий