6777. Автобус

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

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

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

Пример входа	Пример выхода
2 1 3	1 7

РЕШЕНИЕ

элементарная задача – битовые операции

Анализ алгоритма

Пусть изначально в автобусе будет n = 7 людей.

На первой остановке выйдет половина, то есть 3.5 пассажиров и еще полпассажира. Итого останется 3 человека.

На второй остановке выйдет половина, то есть 1.5 пассажиров и еще полпассажира. Итого останется 1 человек.

На третьей остановке выйдет половина, то есть 0.5 пассажиров и еще полпассажира. Автобус оказался пустым.

Если автобус совершит k остановок, то для того чтобы смогли произойти все описанные в условии события, необходимо чтобы в автобусе изначально находилось 2^k – 1 пассажиров.

Реализация алгоритма

Читаем входные данные. Для каждого значения k выводим 2^k – 1.

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&k);

printf("%d\n",(1 << k) - 1);

}

Java реализация

import java.util.*;

public class HelloWorld

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

while(tests-- > 0)

{

int k = con.nextInt();

System.out.println((1 << k) - 1);

}

}

}