Монетки

Автор и разработчик задачи: Даниил Голов

Нам дана последовательность из $$$n$$$ цифр $$$0$$$ или $$$1$$$. Затем, продолжается следующий процесс:

Нужно либо сказать, за какое количество операций процесс остановится, либо, что он будет продолжаться бесконечно.

Рассмотрим инвертирование элемента на позиции $$$k$$$. Заметим, что до инвертирования существовал элемент на позиции $$$\ge k$$$, равный $$$1$$$. Пусть он находился на позиции $$$q$$$. Тогда сначала $$$q - k$$$ раз мы заменим $$$0$$$ на $$$1$$$ на позициях $$$[k, q)$$$, затем элемент на позиции $$$q$$$ поменяется с $$$1$$$ на $$$0$$$, и затем еще $$$q - k$$$ раз мы заменим $$$1$$$ на $$$0$$$ на позициях $$$[k, q)$$$. Таким образом, мы сделаем $$$(q - k) \cdot 2 + 1$$$ операций, после чего количество единиц уменьшится на $$$1$$$. Отсюда следует, что процесс всегда конечный. А также, отсюда понятен алгоритм решения задачи за время $$$O(n \cdot \log(n))$$$. Нужно поддерживать множество позиций $$$1$$$, и за один раз обрабатывать удаление одной единицы.