Сложность: 55%
Есть шарики, пронумерованные от до . Также поступают запросов:
add x
- добавить в дек шарик с номером . Вы можете положить шарик либо сверху, либо снизу дека.del x
- удалить из дека шарик с номером . Вы находите шарик с номером в деке, достаете все шарики НИЖЕ , удаляете шарик , потом кладете достанные шарики (без ) обратно в том же порядке.На запросы -го типа вы тратите действие, а на запросы -го типа - действий, где - количество шариков, которые лежат ниже удаляемого (то есть вы сначала достаете шариков, потом удаляете нижний, потом кладете достанные шариков обратно в том же порядке).
Посчитайте, какое минимальное количество действий вы можете потратить.
Входные данные
Первая строка содержит числа и () - максимальный номер шарика и количество запросов. Далее следуют строк в формате:
add x
- добавить шарик с номером () в начало или конец дека.del x
- удалить шарик с номером () из дека.Гарантируется, что никакой шарик не добавляется 2 раза, а также, что если есть запрос удаления шарика , то он присутствует в деке в данный момент.
Выходные данные
Выведите единственное число - минимальное количество операций, которое вы можете потратить на запросы.
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
1 | 15 | - | |
2 | 15 | 1 | В деке всегда не больше 6 элементов, |
3 | 10 | 2 | В деке всегда не больше 10 элементов, |
4 | 25 | 3 | |
5 | 5 | 3 | |
6 | 30 | 4, 5 | Нет дополнительных ограничений |
STDIN | STDOUT |
2 4 add 1 del 1 add 2 del 2 | 4 |
8 6 add 5 add 8 del 5 add 1 add 4 del 1 | 6 |