Джон отважно боролся за спасение одичалых, атакованных белыми ходоками в Суровом Доме. По прибытию Сэм говорит, что хочет направиться в Старомест, чтобы тренироваться в Цитадели и стать мейстером. Так он сможет вернуться и занять место покойного Эймона, как мейстер Черного Замка. Джон согласился с предложением Сэма, и Сэм отправляется в свое путешествие в Цитадель. Однако становление учащимся Цитадели не так легко, и поэтому мейстеры в Цитадели предложили Сэму задачу, чтобы протестировать его соответствие требованиям.
Изначально у Сэма есть список с единственным числом n. Далее он выполняет некоторые операции над этим списком. На каждой операции Сэм должен удалить любой такой элемент x, что x > 1, из списка, и вставить вместо него три новых элемента , , последовательно. Он должен делать эти операции до тех пор, пока все элементы в списке не равны 0 или 1.
Теперь мейстеры хотят знать общее число единиц на позициях с l-й по r-ю в списке. Сэм хочет стать великим мейстером, но, к сожалению, он не может решить эту задачу. Можете ли вы помочь Сэму пройти тест на соответствие?
Первая строка содержит три целых числа n, l, r (0 ≤ n < 250, 0 ≤ r - l ≤ 105, r ≥ 1, l ≥ 1) — изначальный элемент и диапазон позиций с l-й по r-ю.
Гарантируется, что r не превосходит длины получившегося списка.
Выведите общее число единиц на позициях с l-й по r-ю в получившемся списке.
7 2 5
4
10 3 10
5
Рассмотрим первый тестовый пример:
Список чисел со 2-й по 5-ю позиции содержит числа [1, 1, 1, 1]. Количество единиц равно 4.
Второй тестовый пример:
Список чисел с 3-й по 10-ю позиции содержит числа [1, 1, 1, 0, 1, 0, 1, 0]. Количество единиц равно 5.
Название |
---|