infinit
Разглеждаме
редица,
образувана
по следния
начин:
- първоначално,
редицата е "1";
- последователно
на стъпки се
извършва
следната
трансформация
с редицата:
"1" -> "10" и "0" -> "1".
След безброй
много стъпки
получаваме
редицата "1011010110110101101...".
Задават се Q въпроса
от вида: колко
знака 1 са в
редицата
между
позициите с
номера a и b ?
Задача
Напишете
програма,
която дава
отговорите
на Q-те въпроса.
Вход
Първият ред
на входния
файл infinit.in съдържа
числото Q. Всеки
от
следващите Q реда
съдържа
двойка от
числа a, b, разделени
с интервал.
Изход
Файлът infinit.out трябва
да се състои
от Q реда,
като i–тият
съдържа
отговора за
двойката (a, b) от (i+1)-ия ред на
входния файл.
Ограничения
Пример
infinit.in |
infinit.out |
1 |
4 |
Time limit: 0.1 секунди за тест
Tiberiu-Lucian Florea
University of Bucharest, Mathematics & IT Department
Contact: tiberiu.florea@gmail.com
Български
превод: Емил
Келеведжиев