Задание 4. Поиск минимумов

Задание 4.1. Стек минимумов

Шаблон кода на replit

Сделать стек на основе односвязного списка, у которого трудоемкость взятие минимума, вставка в стек и удаление из него за O(1).

Связный список надо написать самим.

Операции:

  • вставить в конец стека
  • удалить последний элемент стека
  • выдать минимальный элемент в стеке

Входные данные

На вход программы подаются команды, их количество не превышает 100_000. В каждой строке находится одна из команд:

  • push k — положить число k в стек.
  • pop k — убрать последний элемент в стеке.
  • top - выдать последний элемент в стеке.
  • min - выдать текущий минимум в стеке.

Тип данных k — int.

Гарантируется, что некорректные команды подаваться НЕ будут.

Выходные данные

Вывести результат выполнения команд top и min в консоль.

Пример

Вход

push 42
top
min
push 12
min
push 13
top
min
pop
pop
min

Выход

42
42
12
13
12
42

Задание 4.2 Очередь с приоритетом на основе Кучи

Шаблон кода

Разработать структуру данных Очередь, выполняющую следующие операции:

  1. Вставить в очередь за O(log(n))O(log(n)).
  2. Извлечь максимальный элемент O(log(n))O(log(n)).
  3. Увеличить i-ый элемент на v.

Все операции вставки в очередь вводятся по очереди и нумеруются с 1.

При извлченении элемента из очереди, нужно вывести в стандартый поток вывода сам элемент и номер операции, когда его добавили.

То есть в структуре данных надо хранить само значение элемента и номер операции, когда его добавили.

Входные данные

На вход программы подаются команды, их количество не превышает 100_000. В каждой строке находится одна из команд:

  • enqueue k — вставить в очередь число k.
  • dequeue_max — извлечь из очереди максимальный элемент.
  • inc i v - найти элемент вставленныей на i-ой операции и увеличить его на v. Если элемента уже нет, то ничего не делать.

Тип данных k, v — int, i — unsigned int.

Гарантируется, что некорректные команды подаваться НЕ будут.

Выходные данные

Команда dequeue-max печатает в консоль номер операции i, когда элемент был вставлен, и сам элемент k.

Если очередь пустая, то печатаем *.

Пример

Вход

enqueue 10
enqueue 42
enqueue 9
dequeue_max
inc 3 10
dequeue_max
dequeue_max
dequeue_max

Выход

2 42
3 19
1 10
*