Задача T. Робот, налево! ≡
| Автор: | Г. Гренкин | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt |
Условие
В Центре робототехники изобрели робота, который ходит только налево.
На вопрос "зачем?" он затрудняется ответить.
Робот занимает одну клеточку и действует по следующему алгоритму.
- Развернуться влево.
- Если следующая клеточка не была посещена ранее, то пойти прямо (1). Иначе развернуться вправо и пойти прямо (2).
За шаг вида (1) робот получает 1 очко, за шаг вида (2) — 0 очков. Сколько очков получит робот, сделав N шагов?
Формат входного файла
Входной файл содержит целое число N.
Формат выходного файла
Выходной файл должен содержать число очков.
Ограничения
1 ≤ N ≤ 109
Примеры тестов
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|