A. Оптимизация

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

Решая одну из таких оптимизационных задач, Вася свёл её к следующей:

1. дано целое положительное число n,
2. необходимо посчитать количество чисел k (1 ≤ k ≤ n) таких, что k xor 2k xor 3k = 0.

Формат входного файла

Во входном файле содержится единственное число n (1 ≤ n ≤ 10¹⁸).

Формат выходного файла

В выходной файл выведите целое число – количество чисел k, удовлетворяющих описанному выше условию.

Пример:

Операция xor – это операция "исключающее или", которая применяется побитово к разрядам чисел. Таблица истинности определяет для всевозможных пар битов, какое значение будет принимать операция исключающего или для них:

Рассмотрим пример: 5 xor 3. В битовом представлении число 5 представляется как 101, число 3 – 11. Поразрядное применение исключающего или (начиная с младших разрядов) дает:

Пояснение ко второму примеру
Во входном файле содержится n равное 9. Для этого числа подходят следующие значения k, которые дают верное тождество: 1, 2, 4, 5, 8, 9.

Источник: Муниципальный этап всероссийской олимпиады школьников по информатике, 2013-2014 учебный год

Обсудить       Отправить решение



Версия для печати