A. Оптимизация
| Имя входного файла: | bitty.in |
| Имя выходного файла: | bitty.out |
| Ограничение по времени: | 2 s |
| Ограничение по памяти: | 256 megabytes |
В компании KTP SOLUTIONS программисты часто сталкиваются с различными оптимизационными задачами. Вася очень рад задачам такого рода и прилагает массу усилий, чтобы его решения были отточены и отполированы до мелочей. В основном ему приходится работать с оптимизацией данных, поэтому он провел много времени, сжимая данные с помощью различных ухищрений над битами.
Решая одну из таких оптимизационных задач, Вася свёл её к следующей:
- дано целое положительное число n,
- необходимо посчитать количество чисел k (1 ≤ k ≤ n) таких, что k xor 2k xor 3k = 0.
Формат входного файла
Во входном файле содержится единственное число n (1 ≤ n ≤ 1018).
Формат выходного файла
В выходной файл выведите целое число – количество чисел k, удовлетворяющих описанному выше условию.
Пример:
| bitty.in | bitty.out |
|---|---|
| 3 | 2 |
| 9 | 6 |
Операция xor – это операция "исключающее или", которая применяется побитово к разрядам чисел. Таблица истинности определяет для всевозможных пар битов, какое значение будет принимать операция исключающего или для них:
| X | Y | X xor Y |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Рассмотрим пример: 5 xor 3. В битовом представлении число 5 представляется как 101, число 3 – 11. Поразрядное применение исключающего или (начиная с младших разрядов) дает:
| 101 |
| 011 |
| 110 |
Пояснение ко второму примеру
Во входном файле содержится n равное 9. Для этого числа подходят следующие значения k, которые дают верное тождество:
1, 2, 4, 5, 8, 9.
Источник: Муниципальный этап всероссийской олимпиады школьников по информатике, 2013-2014 учебный год
Обсудить
Отправить решение