Корова по имени Бесик красит забор Фермеру Арсену. Бесик начинает в позиции 0 и выполняет последовательность из N операции. (1 <= N <= 100,000) вида "10 L", что означает покрасить 10 единиц влево и "15 R", что означает покрасить 15 единиц вправо. Бесик может уйти не далее чем на 109 единиц от исходной точки.
По имеющей инструкции Арсен хочет узнать область забора, которая покрашена как минимум двумя слоями краски.
Входные данные
В первой строке дается число N(1≤N≤105). Далее каждая из N строк описывает одну из N инструкций.
Выходные данные
Выведите ответ на задачу
Пример
входные данныеСкопировать
6
2 R
6 L
1 R
8 L
1 R
2 R
выходные данныеСкопировать
6
Любой язык
472
Объяснение:
Числe в двоичной системе счисления, состоящему из n единиц, в десятичной системе счисления соответствует число 2^n-1.
Например:
Десятичная Двоичная система
система счисления система счисления
2^1-1=1 1
2^2-1=3 11
2^3-1=7 111
2^8-1=255 111111
Извлечем логарифм из числа 4567 по основанию два и возьмем из полученного результата целую часть.
[㏒
4567]=12
2^12=4096
Вычтем из полученного числа 1
4096-1=4095
Полученному числу соответствует 12 единиц в двоичной системе счисления.
Теперь остается найти искомое число:
4567-N=4095
N=4567-4095=472
X равен 9.
Объяснение:
>>Целые числа на отрезке от 2 до 18 делятся без остатка только на 1. >>При этом сумма чисел только на одном этом отрезке будет равна 170. >>А на втором отрезке от 4 до 20, сумма чисел кратных 4 равно 60. >>Откуда взялось 87 - непонятно.
Да все ок, только небольшая ошибка в логике. Суммарно, оба множества составляют 87. При этом, как правильно указано в первом ответе, сумма чисел множества правой половины составляет 60. Соответственно, сумма чисел множества левого выражения составляет 87-60=27.
Отсюда, сумма чисел (НЕ (A<2 ИЛИ A>18 ИЛИ A%X<>0)) = 27.
Немного преобразуем формулу множества:
А>=2 И А<=20 И A%Х=0, то есть, это числа от 2 до 20 включительно, которые без остатка делятся на Х. И при этом их сумма равна 27.
Очевидно, что это числа 9 и 18. Сумма которых равна 27.