Решение задачи #23. Python Яндекс CodeRun, Гоблины и шаманы

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Гоблины и шаманы.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Гоблины Мглистых гор очень любят ходить к своим шаманам. Так как гоблинов много, к шаманам часто образуются очень длинные очереди. А поскольку много гоблинов в одном месте быстро образуют шумную толпу, которая мешает шаманам проводить сложные медицинские манипуляции, последние решили установить некоторые правила касательно порядка в очереди.

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

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

Формат ввода (input):
В первой строке входных данный записано число N (1≤N≤1051≤N≤10 в пятой степени)— количество запросов к программе. Следующие N строк содержат описание запросов в формате:

''+ i'' — гоблин с номером i (1≤i≤N1≤i≤N) встает в конец очереди.
''* i'' — привилегированный гоблин с номером i встает в середину очереди.
''-'' — первый гоблин из очереди уходит к шаманам. Гарантируется, что на момент такого запроса очередь не пуста.

Формат вывода (Output):
Для каждого запроса типа ''-'' программа должна вывести номер гоблина, который должен зайти к шаманам.

Решение:

Python

import sys
from collections import deque

def main():
    # Используем два deque для эффективного управления очередью
    left = deque()  # Первая половина очереди
    right = deque()  # Вторая половина очереди
    output = []  # Для хранения результатов запросов типа '-'

    # Чтение количества запросов
    n = int(sys.stdin.readline())

    for _ in range(n):
        query = sys.stdin.readline().strip()

        if query.startswith('+'):
            # Обычный гоблин встает в конец очереди
            _, i = query.split()
            right.append(i)
        elif query.startswith('*'):
            # Привилегированный гоблин встает в середину очереди
            _, i = query.split()
            # Вставляем в конец первой половины
            left.append(i)
        elif query == '-':
            # Первый гоблин уходит к шаманам
            if not left:
                # Если первая половина пуста, берем из второй
                output.append(right.popleft())
            else:
                # Иначе берем из первой половины
                output.append(left.popleft())

        # Балансировка очереди
        # Если первая половина меньше второй, перемещаем элемент
        if len(left) < len(right):
            left.append(right.popleft())
        # Если первая половина больше второй, перемещаем элемент
        elif len(left) > len(right) + 1:
            right.appendleft(left.pop())

    # Вывод результатов всех запросов типа '-'
    print('\n'.join(output))

if __name__ == "__main__":
    main()
	

Объяснение кода

Задача заключается в управлении очередью гоблинов, где обычные гоблины встают в конец очереди, а привилегированные — в середину. При этом необходимо эффективно обрабатывать три типа запросов:

Добавление обычного гоблина в конец очереди.
Добавление привилегированного гоблина в середину очереди.
Удаление первого гоблина из очереди (он уходит к шаманам).

Основные идеи решения
Использование двух deque
Мы используем две очереди: left и right.
left хранит первую половину очереди, а right — вторую половину.
Это позволяет эффективно вставлять элементы в середину и удалять элементы с начала очереди.

Обработка запросов
Обычный гоблин (+ i):
Добавляется в конец right, так как он должен встать в конец очереди.

Привилегированный гоблин (* i)
Добавляется в конец left, что соответствует середине очереди. Если длина очереди нечётная, он встаёт сразу за центром.

Удаление гоблина (-)
Если left не пуст, удаляем гоблина из начала left.
Если left пуст, удаляем гоблина из начала right.

Балансировка очереди
После каждого запроса проверяем баланс между left и right.
Если left меньше right, перемещаем элемент из начала right в конец left.
Если left больше right более чем на 1, перемещаем элемент из конца left в начало right.
Это гарантирует, что left всегда содержит первую половину очереди, а right — вторую.

Эффективность
Все операции (append, popleft, appendleft, pop) выполняются за O(1), что делает решение эффективным даже для больших значений N (до 10^5).

Пример работы
Рассмотрим пример входных данных:
7
+ 1
+ 2
* 3
+ 4
-
-
-
1. Гоблин 1 встает в конец: left = [], right = [1].
2. Гоблин 2 встает в конец: left = [], right = [1, 2].
3. Привилегированный гоблин 3 встает в середину: left = [3], right = [1, 2].
4. Гоблин 4 встает в конец: left = [3], right = [1, 2, 4].
5. Балансировка: left = [3, 1], right = [2, 4].
6. Первый гоблин (3) уходит: left = [1], right = [2, 4].
7. Первый гоблин (1) уходит: left = [], right = [2, 4].
8. Первый гоблин (2) уходит: left = [], right = [4].

Вывод:
1
3
2

Преимущества решения
Корректность: Решение правильно обрабатывает все типы запросов и поддерживает баланс очереди.
Эффективность: Временная сложность O(1) для каждой операции.
Простота: Код легко читается и понимается благодаря использованию двух deque и балансировки.

Источник решения: hdhai.com