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

Имя входного файла: bitty.in
Имя выходного файла: bitty.out
Ограничение по времени: 2 s
Ограничение по памяти: 256 megabytes

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

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

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

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

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

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

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

Пример:

bitty.inbitty.out
3 2
9 6

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

XYX xor Y
0 0 0
0 1 1
1 0 1
1 1 0

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

101
011
110
Таким образом, 5 xor 3 = 6.

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


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

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



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