Олимпиадный тренинг

Задача . A2. Коллективный разум (средняя)


Задача

Темы: *2300

Продолжаем банкет! Хайди уже знает, сколько минимум мозгов должно быть в сундуке, чтобы она смогла забрать хотя бы один. Однако же отправиться одной в гущу диких и голодных зомби было достаточно рискованным приключением. Теперь Хайди интересно: чему равняется минимально возможное количество мозгов в сундуке, при котором она смогла бы выбраться с вечеринки живой (возможно с пустыми руками)?

Правила вечеринки по поеданию мозгов остаются такими же как в предыдущей подзадаче: присутствуют n - 1 зомби и Хайди, мозги распределяются по такой же схеме, при которой предложение должны принять как минимум половина присутствующих, чтобы Хайди осталась в живых.

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

В единственной строке входных данных содержится одно целое число n — количество присутствующих на вечеринке (1 ≤ n ≤ 109).

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

Выведите одно целое число: минимальное количество мозгов в сундуке, при котором у Хайди есть надежда выжить.


Примеры
Входные данныеВыходные данные
1 1
0
2 3
1
3 99
49

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя