Решение задачи #17. Python Яндекс CodeRun, Конвеер

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

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

накопитель перемещает первый контейнер из ленты в цех В;

накопитель перемещает первый контейнер из строки в склад (в складе каждый следующий контейнер помещается на предыдущий);

накопитель перемещает верхний контейнер из склада в цех В.

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

Решение:

Python
def main():
    import sys
    input = sys.stdin.read
    data = input().splitlines()

    # Читаем количество тестов
    N = int(data[0])  # Количество тестов
    results = []  # Список для хранения результатов

    # Обработка каждого теста
    for test in range(1, N + 1):
        # Читаем данные для текущего теста
        test_data = list(map(float, data[test].split()))
        K = int(test_data[0])  # Количество контейнеров
        urgencies = test_data[1:]  # Степени срочности контейнеров

        # Моделируем процесс сортировки
        stack = []  # Стек для хранения контейнеров (склад)
        expected = sorted(urgencies)  # Ожидаемый порядок (от меньших к большим)
        sorted_index = 0  # Индекс для проверки ожидаемого контейнера

        # Проверяем поступающие контейнеры
        for container in urgencies:
            # Если текущий контейнер соответствует ожидаемому порядку
            while stack and stack[-1] == expected[sorted_index]:
                stack.pop()  # Убираем контейнер со склада
                sorted_index += 1

            if container == expected[sorted_index]:
                sorted_index += 1
            else:
                stack.append(container)  # Помещаем контейнер на склад

        # Проверяем оставшиеся контейнеры на складе
        while stack and stack[-1] == expected[sorted_index]:
            stack.pop()
            sorted_index += 1

        # Если удалось упорядочить все контейнеры, результат 1, иначе 0
        if sorted_index == K:
            results.append(1)
        else:
            results.append(0)

    # Выводим результаты
    sys.stdout.write("\n".join(map(str, results)) + "\n")


if __name__ == '__main__':
    main()

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

Чтение входных данных:
Первая строка содержит количество тестов N.
Каждая из следующих N строк описывает один тест: количество контейнеров K и их степени срочности.

Логика сортировки:
Создается стек (stack) для моделирования склада.
Список expected содержит степени срочности в порядке, который мы хотим достичь.
Переменная sorted_index отслеживает текущий ожидаемый контейнер.

Обработка каждого контейнера:
Если верхний контейнер на складе соответствует ожидаемому, он перемещается в цех B.
Если текущий контейнер соответствует ожидаемому, он сразу отправляется в цех B.
В противном случае контейнер помещается на склад.

Проверка остатка на складе:
После обработки всех контейнеров оставшиеся на складе элементы проверяются на соответствие порядку.

Определение результата:
Если все контейнеры упорядочены, добавляем результат 1. В противном случае 0.

Вывод результатов:
Для каждого теста результат выводится на отдельной строке.

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