e-olymp
Yarışlar

Recursion + memorization

Уровень Саурмана

Армия орков Сарумана и других темных сил непрерывно добывает уголь и собирает лесоматериалы на земле вокруг своей мощной башни в течении n дней. В день номер i Саруман решает либо тратить ресурсы на добычу угля и уборку большего количества леса, или на повышение уровня (т.е., высоты) его башни. Он увеличивает уровень своей башня на одну единицу только в те дни, когда бинарное представление числа i содержит общее количество единиц, кратное 3. Начальный уровень башне в день 0 равен нулю.

Например, Саурман увеличит высоту своей башни в день 7 (бинарный код 111), далее в день 11 (бинарный код 1011), затем в дни 13, 14, 19 и так далее.

Саурман хочет предвидеть высоту своей башни через n дней. Напишите программу, которая ему поможет в этом.

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

Состоит из нескольких тестов. Каждый тест расположен в отдельной строке и содержит натуральное число n (n < 1016).

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

Для каждого теста выведите строку: "Day n: Level = l", где n - входное значение n, а l - количество уровней башни после n дней.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
2
19
64
Çıxış verilənləri
Day 2: Level = 0
Day 19: Level = 5
Day 64: Level = 21
Mənbə 2012 North America - Pacific Northwest Region Programming Contest, Ноябрь 3, Задача G