Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Виталя и Рома

(Время: 2 сек. Память: 16 Мб Сложность: 60%)

Рома и Виталя придумали следующую игру: на скорость прибавлять и вычитать из числа степени двойки, а после каждой операции считать число единиц в двоичной записи этого числа. Кто быстрее и правильнее, тот и победил.

Вам предстоит помочь им: написать программу, с помощью которой они могли бы проверить свои расчеты. Правила игры следующие:

  1. В начале игры число P равно нулю.
  2. За всю игру совершается N операций.
  3. Каждая операция – прибавление к числу P или вычитание из числа P числа 2S.
  4. После выполнения каждой операции необходимо вывести число единиц в двоичной записи числа 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.TXTOUTPUT.TXT
12
add 1
sub 1
1
0
24
add 2
add 8
sub 3
sub 0
1
2
6
7

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Статические RSQ и RMQ
 Sqrt-декомпозиция
 Дерево Фенвика
 Дерево отрезков
 A. Максимумы на отрезках
 B. Число нулей на отрезке
 C. Суперминимум
 D. Билеты на электричку
 E. Виталя и Рома
 F. Sqrt-декомпозиция
 G. Березовая аллея

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru