Нижегородская олимпиада: Задачи олимпиады

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

Узор создается следующим образом. Если бы борт маршрутки был бы бесконечным в две стороны: вправо и вверх, — то узор рисовали бы так. Разделим борт на бесконечное количество вертикальных полос одинаковой (единичной) ширины, занумеруем их слева направо, начиная с единицы. Полосы с нечетными номерами красить серой краской вообще не будем. Полосы, номера которых делятся на два, но не делятся на четыре, закрасим снизу до высоты, равной единице длины (т.е. образуется серый квадрат). Полосы, номера которых делятся на четыре, но не делятся на восемь, закрасим снизу до высоты, равной двум единицам длины; полосы, номера которых делятся на восемь, но не делятся на 16 — до высоты, равной 3; номера которых делятся на 16, но не делятся на 32 — до высоты, равной 4, и т.д.

Получим следующий узор:

Естественно, у реальных маршруток ширина борта ограничена (высоту мы для простоты будем считать неограниченной). Можно было бы на каждой маршрутке рисовать начало такого узора, но это не интересно — поэтому было решено для каждой маршрутки выбрать два числа, \(l\) и \(r\), и нарисовать на борту фрагмент этого узора с \(l\)-ого столбика по \(r\)-ый включительно. Определите, сколько на это уйдет серой краски, считая, что единица краски уходит на единичный квадрат узора.