Склад-гармошка
Склад снимает залы, и вместимость зала всегда степень двойки: 1, 2, 4, 8… коробок. Сначала склад пуст и занимает зал на одну коробку. Коробки привозят и увозят по одной, и правила переездов строгие.
- Если нужно поставить коробку, а зал полон, склад снимает зал вдвое больше и перевозит туда все коробки. Потом ставит новую.
- Если после того как коробку увезли, коробки занимают малую долю зала, склад переезжает в зал вдвое меньше и тоже перевозит все коробки. Зал меньше чем на одну коробку не бывает.
Директор спорит с бухгалтером, когда считать долю малой. Директор говорит: съезжать, как только занята половина зала или меньше. Бухгалтер: только когда занята четверть или меньше. Посчитайте по журналу склада, сколько коробок перевезут грузчики за все переезды по правилу директора и по правилу бухгалтера.
Вход
В первой строке число записей журнала q (1 ≤ q ≤ 200 000). В каждой из следующих строк — знак и число: + k — привезли k коробок, - k — увезли k коробок (1 ≤ k ≤ 10⁹). Увозят только то, что есть на складе. Коробки внутри одной записи привозят и увозят по одной, и после каждой проверяются правила.
Выход
Два числа через пробел: сколько коробок перевезут по правилу директора (половина) и по правилу бухгалтера (четверть). Ответы помещаются в 64-битное целое.
Примеры
Пример 1
4 + 5 - 3 + 6 - 7
26 16
Пример 2
7 + 8 + 1 - 1 + 1 - 1 + 1 - 1
55 15
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Это динамический массив: зал — блок памяти, коробки — элементы, переезд — копирование. Правило директора — то самое сжатие при половине, которое в статье раскачивается на качелях. Но сначала о скорости: одна запись «+ 10⁹» — это миллиард коробок. Перебирать их по одной нельзя.
2Подсказка 2
Между переездами коробки просто прибавляются или убавляются. Сколько коробок можно привезти до ближайшего переезда? А увезти?
3Идея
Двигаемся не по коробкам, а от переезда к переезду. При привозе k коробок до переезда помещается cap − size: если k не больше, просто прибавляем. Иначе заполняем зал до краёв, переезжаем (перевозим cap коробок), удваиваем зал и продолжаем с остатком. При вывозе зал сжимается, когда коробок становится cap / t (t = 2 у директора, 4 у бухгалтера). Если после вывоза k коробок их останется больше, переезда нет. Иначе увозим ровно до порога, перевозим оставшиеся, делим зал пополам и продолжаем. Каждый переезд меняет зал вдвое, поэтому на одну запись приходится не больше пары сотен шагов.
4Разбор
Одна функция simulate(events, t), вызванная дважды. Пограничные случаи: зал на одну коробку никогда не сжимается; у бухгалтера зал на две коробки сжимается, только когда коробок ноль (четверть от двух — меньше одной коробки). Первый пример по правилу директора: пять коробок — переезды при 1, 2 и 4 коробках, перевезли 7. Первая же увезённая коробка оставляет 4 из 8 — ровно половину: переезд в зал на 4, перевезли 4. Третья оставляет 2 из 4 — снова половина: в зал на 2, ещё 2. Дальше досчитайте сами и сверьтесь с ответом 26.
Второй пример — качели: полный зал на 8 коробок, и коробку то привозят, то увозят. У директора каждая такая пара — два переезда по 8 коробок, у бухгалтера после первого расширения переездов нет вовсе. На четвёртом тесте то же самое при 2²⁹ коробках: по правилу директора грузчики перевезут больше 10¹⁴ коробок, по правилу бухгалтера — около миллиарда. Это и есть причина, по которой динамические массивы сжимаются при четверти, а не при половине.
4+Решение
5Сложность
На запись «+ k» — O(1 + число удвоений), на «− k» — O(1 + число сжатий). Зал не может удвоиться больше 60 раз подряд, так что всего O(q · log N), где N — наибольшее число коробок.
6Типичные ошибки
- По одной коробке. Верно и просто, но третий тест — это два миллиарда шагов.
- Сжатие при «меньше», а не «не больше». По условию переезд случается, когда занята ровно половина (или четверть) — граница включается.
- Сжатие сразу на несколько ступеней. Если увезли почти всё, зал сжимается не сразу в нужный размер, а ступенями, и на каждой ступени перевозят все оставшиеся коробки. Поэтому после сжатия нужно снова проверить порог.
- 32-битный счётчик. По правилу директора ответ доходит до 10¹⁴.