Задачник Базовый курс EN

Счётчик туда-обратно

Счётчик хранит число из k бит и умеет две операции: + — прибавить единицу, - — вычесть единицу. Счёт идёт по кругу: после 2^k − 1 идёт 0, а перед 0 — 2^k − 1. Каждый бит, который меняется при операции, — это переключение: например, при переходе от 0111 к 1000 переключаются все четыре бита.

Счётчик начинает с числа v и выполняет последовательность операций. Сколько всего переключений бит произойдёт и сколько их было за одну операцию самое большее?

Вход

В первой строке k, v и n (1 ≤ k ≤ 62, 0 ≤ v < 2^k, 1 ≤ n ≤ 10⁶). Во второй — строка из n символов + и -.

Выход

Два числа: всего переключений и наибольшее число переключений за одну операцию.

Примеры

Пример 1

Вход

4 0 8
++++++++

Выход

15 4

Ограничения

Время · Python: 2500 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 10 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Какие биты переключились при переходе от v к w? Ровно те, в которых v и w различаются.

2Идея

Число различающихся бит — это число единиц в v XOR w. Новое значение считается за одну операцию: (v ± 1), обрезанное до k бит маской 2^k − 1, — маска заодно делает переход через край круга. Единицы в числе считает встроенная функция: int.bit_count() в Python, bits.OnesCount64 в Go. Каждая операция — O(1), сколько бы бит она ни переключила.

3Разбор

Естественное решение — переключать биты по одному, как при сложении столбиком: прибавление стирает хвост из единиц и ставит одну единицу, вычитание стирает хвост из нулей и ставит один ноль. Пока операции только прибавляют, это быстро: в статье об амортизационном анализе доказано, что n прибавлений с нуля переключают меньше 2n бит. Но доказательство опирается на монеты, которые лежат на единицах, а вычитание тратит их не в ту сторону. Счётчик, который стоит на 2⁶¹ − 1 и выполняет +-+-…, каждый раз переключает все 62 бита: 0111…1 ↔ 1000…0. Так устроен четвёртый тест: миллион операций, 62 миллиона переключений, и поштучное решение на Python не успевает.

Ответ при этом может быть большим — до 62·10⁶ — но в 64-битное целое помещается.

В примере 8 прибавлений с нуля: переключений 1, 2, 1, 3, 1, 2, 1 и 4 — всего 15, меньше 2 · 8. Для прибавлений подряд есть и формула: от 0 до n бит номер j переключается ⌊n/2^j⌋ раз, и сумма по всем битам равна 2n минус число единиц в записи n.

3+Решение

4Сложность

O(n): каждая операция — несколько действий над 64-битным числом.

5Типичные ошибки

Переключать по одному биту. Верно, но на чередовании у границы — 62 шага на операцию.
Забыть про круг. Прибавление к 2^k − 1 переключает все k бит и даёт 0; вычитание из 0 — тоже k бит. Без маски получится число из k + 1 бит или отрицательное.
Отрицательные числа в Python. (0 − 1) & маска даёт 2^k − 1, как и нужно; без маски bit_count посчитает единицы в −1, то есть одну.

Алгоритмы задачи

TEC Приём Амортизационный анализ Оценка всей последовательности операций, а не каждой: суммой, монетами и потенциалом — и где она не спасает. оценка на последовательность 2 задачи TEC Приём Битовые трюки Число как набор флажков: маски, младшая единица, подсчёт единиц и перебор подмножеств без рекурсии. O(1) на операцию над словом 1 задача