Условие

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

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

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

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

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

Примеры

Ввод: 2 2 2.9 2.1 3 5.6 9.0 2.0 Вывод:

1 0

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.ArrayDeque

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))
    
    // Читаем количество тестов
    val t = reader.readLine().trim().toInt()
    
    repeat(t) {
        // Считываем одну строку теста, где первое число — количество контейнеров, далее K чисел (срочность контейнеров)
        val tokens = reader.readLine().trim().split("\\\\s+".toRegex())
        val k = tokens[0].toInt()
        // Сохраняем контейнеры (их степень срочности) в порядке поступления
        val containers = tokens.subList(1, 1 + k).map { it.toDouble() }
        // Желаемый порядок доставки: по возрастанию срочности (меньшим числам соответствует большая срочность)
        val sorted = containers.sorted()
        
        // Стек, моделирующий склад (накопитель)
        val stack = ArrayDeque<Double>()
        var expectedIndex = 0  // индекс следующего контейнера, который должен быть отправлен в цех В
        
        // Симулируем процесс: проходим по всем контейнерам поступления
        for (container in containers) {
            // Перемещаем контейнер с ленты в склад (аналогично перемещению в накопитель, откуда его можно направить в В)
            stack.addLast(container)
            // После каждого перемещения проверяем, можно ли извлечь один или несколько контейнеров из склада,
            // чтобы они соответствовали следующему ожидаемому контейнеру в отсортированном порядке.
            while (stack.isNotEmpty() && stack.last() == sorted[expectedIndex]) {
                stack.removeLast()  // извлекаем контейнер из склада в цех В
                expectedIndex++       // следующий ожидаемый контейнер
                if (expectedIndex == k) break
            }
            if (expectedIndex == k) break
        }
        
        // Если извлекли все контейнеры в нужном порядке, то упорядочивание возможно.
        writer.write(if (expectedIndex == k) "1" else "0")
        writer.newLine()
    }
    
    writer.flush()
    writer.close()
    reader.close()
}