Виталя и Рома
(Время: 2 сек. Память: 16 Мб Сложность: 60%)
Рома и Виталя придумали следующую игру: на скорость прибавлять и вычитать из числа степени двойки, а после каждой операции считать число единиц в двоичной записи этого числа. Кто быстрее и правильнее, тот и победил.
Вам предстоит помочь им: написать программу, с помощью которой они могли бы проверить свои расчеты. Правила игры следующие:
- В начале игры число P равно нулю.
- За всю игру совершается N операций.
- Каждая операция – прибавление к числу P или вычитание из числа P числа 2S.
- После выполнения каждой операции необходимо вывести число единиц в двоичной записи числа P.
Гарантируется, что ни в какой момент времени число P не может оказаться отрицательным.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 105) – количество операций. На следующих N строках заданы операции, где каждая операция задается одной из двух строк: «add S» или «sub S», где S (0 ≤ S ≤ 105) – целое число.
Операция «add S» означает, что к числу P нужно прибавить 2S.
Операция «sub S» означает, что из числа P нужно вычесть 2S.
Выходные данные
Для каждого из N запросов в выходной файл OUTPUT.TXT в отдельной строке выведите количество единиц в двоичной записи числа P после выполнения данной операции.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 2 add 1 sub 1 | 1 0 |
2 | 4
add 2
add 8
sub 3
sub 0 | 1
2
6
7 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|