0

Решаю задачу на Яндекс.Контест.

Текст задачи:

Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front() работали корректно. Но, если в деке было много элементов, программа работала очень долго. Дело в том, что не все операции выполнялись за O(1). Помогите Гоше! Напишите эффективную реализацию.

Внимание: при реализации нельзя использовать связный список.

Формат ввода

В первой строке записано количество команд n — целое число, не превосходящее 100000. Во второй строке записано число m — максимальный размер дека. Он не превосходит 50000. В следующих n строках записана одна из команд:

push_back(value) – добавить элемент в конец дека. Если в деке уже находится максимальное число элементов, вывести «error». push_front(value) – добавить элемент в начало дека. Если в деке уже находится максимальное число элементов, вывести «error». pop_front() – вывести первый элемент дека и удалить его. Если дек был пуст, то вывести «error». pop_back() – вывести последний элемент дека и удалить его. Если дек был пуст, то вывести «error». Value — целое число, по модулю не превосходящее 1000.

Формат вывода

Выведите результат выполнения каждой команды на отдельной строке. Для успешных запросов push_back(x) и push_front(x) ничего выводить не надо.

Я нашла на Stackoverflow решение этой задачи на Python.

class Dek:
    def __init__(self, max_size: int):
        self._elements = [None] * max_size
        self._max_size = max_size
        self._head = 0
        self._tail = 0
        self._size = 0

    def is_empty(self):
        return self._size == 0

    def push_back(self, value: int):
        if self._size != self._max_size:
            self._elements[self._tail] = value
            self._tail = (self._tail + 1) % self._max_size
            self._size += 1
        else:
            raise OverflowError

    def push_front(self, value: int):
        if self._size != self._max_size:
            self._elements[self._head - 1] = value
            self._head = (self._head - 1) % self._max_size
            self._size += 1
        else:
            raise OverflowError

    def pop_back(self):
        if self.is_empty():
            raise IndexError
        x = self._elements[self._tail - 1]
        self._elements[self._tail - 1] = None
        self._tail = (self._tail - 1) % self._max_size
        self._size -= 1
        return x

    def pop_front(self):
        if self.is_empty():
            raise IndexError
        x = self._elements[self._head]
        self._elements[self._head] = None
        self._head = (self._head + 1) % self._max_size
        self._size -= 1
        return x


def main():
    count_command = int(input())
    queue_size = int(input())

    queue = Dek(queue_size)
    commands = {
        'push_front': queue.push_front,
        'push_back': queue.push_back,
        'pop_front': queue.pop_front,
        'pop_back': queue.pop_back,
    }
    for i in range(count_command):
        command = input()
        operation, *value = command.split()
        if value:
            try:
                result = commands[operation](int(*value))
                if result is not None:
                    print(result)
            except OverflowError:
                print('error')
        else:
            try:
                result = commands[operation]()
                print(result)
            except IndexError:
                print('error')


if __name__ == '__main__':
    main()

Но мне не до конца понятна вот эта часть кода:

for i in range(count_command):
            command = input()
            operation, *value = command.split()
            if value:
                try:
                    result = commands[operation](int(*value))
                    if result is not None:
                        print(result)
                except OverflowError:
                    print('error')
            else:
                try:
                    result = commands[operation]()
                    print(result)
                except IndexError:
                    print('error')

Объясните, пожалуйста, что происходит в каждой из строчек этой части решения.

1
  • Да, вы правы, я не знала, что правильные ответы нужно помечать зеленой галочкой, исправляю свою оплошность. Спасибо, что обратили мое внимание на это!
    – Leb
    19 фев 2022 в 9:50

1 ответ 1

1

Вводится строка, содержащая название действия и значение-операнд (если нужен)

Она разбивается на две части, одна содержит строку действия, вторая (возможно, пустая) - операнд

Если операнд есть, то вызывается функция из словаря commands (который хранит соответствие строки и соответствующей функции) с этим самым операндом, преобразованным в целое число (например, push_back(3))

Если нет (например, для извлечения операнд не нужен), то выполняется функция без аргумента (типа pop_back)

Остальное - обработка ошибок (ввода, переполнения)

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.