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]

Ссылки

e-olymp 8352. Такси

Такси

В час пик на остановку одновременно подъехали три маршрутных такси, следующие по одному маршруту, в которые тут же набились пассажиры. Водители обнаружили, что количество людей в разных маршрутках разное, и решили пересадить часть пассажиров так, чтобы в каждой маршрутке было поровну пассажиров. Требуется определить, какое наименьшее количество пассажиров придется при этом пересадить.

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

Три натуральных числа, не превосходящих $100$ — количество пассажиров в первой, второй и третьей маршрутках соответственно.

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

Выведите одно число — наименьшее количество пассажиров, которое требуется пересадить. Если это невозможно, выведите слово [latex]IMPOSSIBLE[/latex]  (заглавными буквами).

Тесты

Ввод Вывод
1 1 2 3 1
2 100 100 99 IMPOSSIBLE
3 100 100 100 0
4 19 59 6 31
5 30 9 74 IMPOSSIBLE

Код программы (Линейные вычисления)

Решение

В начале выводим полную формулу. Для этого находим, сколько пассажиров должно быть в одном автобусе после всех перестановок : $\frac{b1 + b2 + b3}{3}$. Далее, от количества пассажиров в каждом автобусе изначально отнимаем требуемое значение. Так как оно может отличаться как в плюс, так и в минус используем модуль : $|b1-need|+|b2-need|+|b3-need|$. А так как «излишки» перераспределяются между оставшимися двумя автобусами, то чтобы избежать повторения мы делим все на $2$ : $\frac{|b1-need|+|b2-need|+|b3-need|}{2}$.

Далее мы вычисляем, существует ли остаток от деления общего количества пассажиров на $3$; для этого используем логическую переменную. Если остаток существует и  f == true  , то  выводится [latex]IMPOSSIBLE[/latex].  Если же f == false , то вычисляется и выводится количество перестановок пассажиров.

 

Код программы (Ветвление)

Решение

Алгоритм решения в данном случае полностью повторяет предыдущий, но с помощью условного оператора мы можем сразу же проверить сумму пассажиров на делимость, вывести [latex]IMPOSSIBLE[/latex] и завершить программу не вычисляя формулы.

Ссылки

Условие задачи на E-Olymp

Код программы на IdeOne (Линейные вычисления)

Код программы на IdeOne (Ветвление)