Очередь с защитой от ошибок python

Стек (stack)

Начнём с самого простого — со стека.
Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по
принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Его очень легко реализовать на базе списка в питоне или вектора в C++.
В качестве примера ниже ссылочная реализация стека:

class _StackItem:
    """Класс _StackItem - один элемент стека.
    Хранит значение и ссылку на предыдущий элемент, или None, если такого нет
    """
    __slots__ = ['value', 'prev']

    def __init__(self, value, prev):
        self.value = value  # Значение
        self.prev = prev  # Ссылка на предыдущий элемент


class Stack:
    """Класс Stack - ссылочная реализация стека.
    """
    __slots__ = ['_len', '_top']

    def __init__(self):
        """Создать пустой стек"""
        self._len = 0
        self._top = None

    def push(self, value):
        """Добавить в стек новое значение"""
        self._top = _StackItem(value, self._top)
        self._len += 1

    def pop(self):
        """Изъять с головы стека значение.
        Бросить ошибку, если стек пуст"""
        if self._top is None:
            raise(IndexError('pop from empty stack'))
        old_top = self._top
        value = old_top.value
        self._top = old_top.prev
        self._len -= 1
        del(old_top)
        return value

    def top(self):
        """Вернуть содержимое вершины стека.
        Бросить ошибку, если стек пуст"""
        if self._top is None:
            raise(IndexError('stack is empty'))
        return self._top.value

    def clear(self):
        """Очистить стек"""
        while self._top:
            old_top = self._top
            self._top = old_top.prev
            del(old_top)
        self._len = 0

    def len(self):
        """Вернуть текущую длину стека"""
        return self._len

################################################################################
# Модульное тестирование класса Stack
# Используем модуль unittest: https://docs.python.org/3.5/library/unittest.html
# Только для ценителей "прекрасного"
import unittest
class TestStack(unittest.TestCase):

    def test_init(self):
        t_stack = Stack()
        self.assertIsNotNone(t_stack)
        self.assertEqual(t_stack.len(), 0)

    def test_one_push_one_pop(self):
        t_stack = Stack()
        t_stack.push(179)
        self.assertEqual(t_stack.top(), 179)
        self.assertEqual(t_stack.len(), 1)
        self.assertEqual(t_stack.pop(), 179)
        self.assertEqual(t_stack.len(), 0)
        self.assertRaises(IndexError, t_stack.pop)
        self.assertRaises(IndexError, t_stack.top)

    def test_10000_push_pop(self):
        t_stack = Stack()
        for i in range(10000):
            self.assertEqual(t_stack.len(), 0, msg='len should be 0')
            t_stack.push(i)
            self.assertEqual(t_stack.len(), 1, msg='len should be 1')
            self.assertEqual(t_stack.top(), i, msg='top should be {}'.format(i))
            self.assertEqual(t_stack.pop(), i, msg='pop should return {}'.format(i))
            self.assertEqual(t_stack.len(), 0, msg='len should be 0')
            self.assertRaises(IndexError, t_stack.pop)
            self.assertRaises(IndexError, t_stack.top)

    def test_10000_push_10000_pop(self):
        t_stack = Stack()
        for i in range(10000):
            self.assertEqual(t_stack.len(), i)
            t_stack.push(i)
            self.assertEqual(t_stack.len(), i + 1)
            self.assertEqual(t_stack.top(), i)
        for i in range(9999, -1, -1):
            self.assertEqual(t_stack.len(), i + 1)
            self.assertEqual(t_stack.pop(), i)
            self.assertEqual(t_stack.len(), i)
        self.assertRaises(IndexError, t_stack.pop)
        self.assertRaises(IndexError, t_stack.top)

    def test_clear_0(self):
        t_stack = Stack()
        t_stack.clear()
        self.assertEqual(t_stack.len(), 0)
        self.assertRaises(IndexError, t_stack.pop)
        self.assertRaises(IndexError, t_stack.top)

    def test_clear_1(self):
        t_stack = Stack()
        t_stack.push(179)
        t_stack.clear()
        self.assertEqual(t_stack.len(), 0)
        self.assertRaises(IndexError, t_stack.pop)
        self.assertRaises(IndexError, t_stack.top)

    def test_clear_10000(self):
        t_stack = Stack()
        for i in range(10000):
            t_stack.push(i)
        t_stack.clear()
        self.assertEqual(t_stack.len(), 0)
        self.assertRaises(IndexError, t_stack.pop)
        self.assertRaises(IndexError, t_stack.top)

    def test_541_stacks(self):
        t_stacks = [Stack() for i in range(541)]
        for i in range(10000):
            cur_stack = t_stacks[i % len(t_stacks)]
            cur_stack.push(i)
            self.assertEqual(cur_stack.top(), i)
            self.assertEqual(cur_stack.len(), i // len(t_stacks) + 1)
        for i in range(9999, -1, -1):
            cur_stack = t_stacks[i % len(t_stacks)]
            self.assertEqual(cur_stack.pop(), i)
            self.assertEqual(cur_stack.len(), i // len(t_stacks))


if __name__ == '__main__':
    unittest.main(verbosity=2)

Очередь (queue)

Очередь (queue) — абстрактный тип данных, представляющий собой список элементов, организованных по
принципу FIFO «первый пришёл — первый вышел» (англ. first in, first out).
В отличие от стека реализация очереди несколько сложнее.
Существует несколько вариантов реализации:

• В массиве/списке фиксированной длины с бегом «по кругу».
  Храним указатели на начало и на конец очереди внутри массива.
  Если доходим до конца массива/списка, то продолжаем с нулевого элемента так, как будто массив склеен в круг.
  
  Достоинства: сложность операций добавления и удаления — всегда $O(1)$.
  
  Недостатки: ограниченная длина, большое потребление памяти на маленьких очередях.
• На двух стеках.
  В один стек мы добавляем элементы, а из другого изымаем.
  Если стек для изымания опустошился, то перекладываем в него элементы из стека для добавления (порядок при этом автоматически обратится).
  При этом каждый элемент, очевидно, будет переложен не более одного раза.
  Однако в моменты перекладывания возникает задержка сложности до $O(n)$.
  
  Достоинства: сложность операций добавления и удаления — в среднем $O(1)$.
  
  Недостатки: иногда возникает задержка для перекладывания из одного стека в другой.
• Ссылочная реализация.
  Примерно как у стека в примере.
  
  Достоинства: сложность операций добавления и удаления — всегда $O(1)$.
  
  Недостатки: большая константа, большое потребление памяти.
• В массиве/списке фиксированной длины с увеличением размера по экспоненте.
  При заполнении всего массива мы создаём новый в $q>1$ раз длинее и перекладываем в него элементы.
  
  Достоинства: сложность операций добавления и удаления — в среднем $O(1)$.
  
  Недостатки: иногда возникает задержка для расширения очереди.

Дек (deque)

Дек (deque) — абстрактный тип данных, представляющий собой список элементов, в которой элементы можно добавлять и удалять как в начало, так и в конец.
Варианты реализации дека примерно такие же, как у очереди (с соответствующими модификациями).

Обратная польская запись

1. Гистограмма

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

Вовочка ломает систему безопасности Пентагона. Для этого ему понадобилось узнать, какие символы в секретных зашифрованных посланиях употребляются чаще других. Для удобства изучения Вовочка хочет получить графическое представление встречаемости символов. Поэтому он хочет построить гистограмму количества символов в сообщении. Гистограмма — это график, в котором каждому символу, встречающемуся в сообщении хотя бы один раз, соответствует столбик, высота которого пропорциональна количеству этих символов в сообщении.

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

Входной файл содержит зашифрованный текст сообщения. Он содержит строчные и прописные латинские буквы, цифры, знаки препинания («.», «!», «?», «:», «-», «,», «;», «(», «)»), пробелы и переводы строк. Размер входного файла не превышает 10000 байт. Текст содержит хотя бы один непробельный символ. Все строки входного файла не длиннее 200 символов.Для каждого символа c кроме пробелов и переводов строк выведите столбик из символов «#», количество которых должно быть равно количеству символов c в данном тексте. Под каждым столбиком напишите символ, соответствующий ему. Отформатируйте гистограмму так, чтобы нижние концы столбиков были на одной строке, первая строка и первый столбец были непустыми. Не отделяйте столбики друг от друга. Отсортируйте столбики в порядке увеличения кодов символов.

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

Для каждого символа c кроме пробелов и переводов строк выведите столбик из символов «#», количество которых должно быть равно количеству символов c в данном тексте. Под каждым столбиком напишите символ, соответствующий ему. Отформатируйте гистограмму так, чтобы нижние концы столбиков были на одной строке, первая строка и первый столбец были непустыми. Не отделяйте столбики друг от друга. Отсортируйте столбики в порядке увеличения кодов символов.

Пример

input.txt

Twas brillig, and the slithy toves
Did gyre and gimble in the wabe;
All mimsy were the borogoves,
And the mome raths outgrabe.

output.txt

         #              
         #              
         #              
         #              
         #              
         #         #    
         #  #      #    
      #  # ###  ####    
      ## ###### ####    
      ##############    
      ##############  ##
#  #  ############## ###
########################
,.;ADTabdeghilmnorstuvwy

Решение

2. Красивая строка

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

Красотой строки назовем максимальное число идущих подряд одинаковых букв. (красота строки abcaabdddettq равна 3)
Сделайте данную вам строку как можно более красивой, если вы можете сделать не более k операций замены символа.

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

В первой строке записано одно целое число k (0 ≤ k ≤ 109)
Во второй строке дана непустая строчка S (|S| ≤ 2 ⋅ 105). Строчка S состоит только из маленьких латинских букв.

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

Выведите одно число — максимально возможную красоту строчки, которую можно получить.

Примеры

input.txt

output.txt

input.txt

output.txt

Решение

3. Коллекционер Диего

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

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

Диего собрал N наклеек, некоторые из которых, возможно, совпадают. Как-то раз к нему пришли K коллекционеров. i-й из них собрал все наклейки с номерами не меньшими, чем pi. Напишите программу, которая поможет каждому из коллекционеров определить, сколько недостающих ему наклеек есть у Диего. Разумеется, гостей Диего не интересуют повторные экземпляры наклеек.

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

В первой строке содержится единственное число N (0 ≤ N ≤ 100 000) — количество наклеек у Диего.

В следующей строке содержатся N целых неотрицательных чисел (не обязательно различных) — номера наклеек Диего. Все номера наклеек не превосходят 109.

В следующей строке содержится число K (0 ≤ K ≤ 100 000) — количество коллекционеров, пришедших к Диего. В следующей строке содержатся K целых чисел pi (0 ≤ pi ≤ 109), где pi — наименьший номер наклейки, не интересующий i-го коллекционера.

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

Для каждого коллекционера в отдельной строке выведите количество различных чисел на наклейках, которые есть у Диего, но нет у этого коллекционера.

Примеры

input.txt

output.txt

input.txt

output.txt

Решение

4. Контрольная работа

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

Петя и Вася — одноклассники и лучшие друзья, поэтому они во всём помогают друг другу. Завтра у них контрольная по математике, и учитель подготовил целых K вариантов заданий.

В классе стоит один ряд парт, за каждой из них (кроме, возможно, последней) на контрольной будут сидеть ровно два ученика. Ученики знают, что варианты будут раздаваться строго по порядку: правый относительно учителя ученик первой парты получит вариант 1, левый — вариант 2, правый ученик второй парты получит вариант 3 (если число вариантов больше двух) и т.д. Так как K может быть меньше чем число учеников N, то после варианта K снова выдаётся вариант 1. На последней парте в случае нечётного числа учеников используется только место 1.

Петя самым первым вошёл в класс и сел на своё любимое место. Вася вошёл следом и хочет получить такой же вариант, что и Петя, при этом сидя к нему как можно ближе. То есть между ними должно оказаться как можно меньше парт, а при наличии двух таких мест с равным расстоянием от Пети Вася сядет позади Пети, а не перед ним. Напишите программу, которая подскажет Васе, какой ряд и какое место (справа или слева от учителя) ему следует выбрать. Если же один и тот же вариант Вася с Петей писать не смогут, то выдайте одно число  - 1.

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

В первой строке входных данных находится количество учеников в классе 2 ≤ N ≤ 109. Во второй строке — количество подготовленных для контрольной вариантов заданий 2 ≤ K ≤ N. В третьей строке — номер ряда, на который уже сел Петя, в четвёртой — цифра 1, если он сел на правое место, и 2, если на левое.

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

Если Вася никак не сможет писать тот же вариант, что и Петя, то выведите  - 1. Если решение существует, то выведите два числа — номер ряда, на который следует сесть Васе, и 1, если ему надо сесть на правое место, или 2, если на левое. Разрешается использовать только первые N мест в порядке раздачи вариантов.

Пример

input.txt

output.txt

input.txt

output.txt

Примечание

В первом примере вариантов 2, поэтому наилучшее место для Васи находится сразу за Петей. Во втором примере Петя будет единственным, кто получит вариант 13.

Решение

5. Хорошая строка

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайта

На день рождения маленький Ипполит получил долгожданный подарок — набор дощечек с написанными на них буквами латинского алфавита. Теперь-то ему будет чем заняться долгими вечерами, тем более что мама обещала подарить ему в следующем году последовательность целых неотрицательных чисел, если он хорошо освоит этот набор. Ради такого богатства Ипполит готов на многое.

Прямо сейчас юный исследователь полностью поглощён изучением хорошести строк. Хорошестью строки называется количество позиций от 1 до L - 1 (где L — длина строки), таких, что следующая буква в строке является следующей по алфавиту. Например, хорошесть строки «abcdefghijklmnopqrstuvwxyz» равна 25, а строки «abdc» — только 1.

Ипполит размышляет над решением закономерно возникающей задачи: чему равна максимально возможная хорошесть строки, которую можно собрать, используя дощечки из данного набора? Вы-то и поможете ему с ней справиться.

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

Первая строка ввода содержит единственное целое число N — количество различных букв в наборе (1 ≤ N ≤ 26). Обратите внимание: в наборе всегда используются N первых букв латинского алфавита.

Следующие N строк содержат целые положительные числа ci — количество букв соответствующего типа (1 ≤ ci ≤ 109). Таким образом, первое число означает количество букв «a», второе число задаёт количество букв «b» и так далее.

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

Выведите единственное целое число — максимально возможную хорошесть строки, которую можно собрать из имеющихся дощечек.

Примеры

input.txt

output.txt

input.txt

output.txt

Примечание

В первом тесте имеется по одной дощечке с каждой из 3 различных букв. Ответ 2 достигается на строке «abc»

Решение

6. Операционные системы lite

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунды

Ограничение по памяти: 64 мегабайт

Васин жесткий диск состоит из M секторов. Вася последовательно устанавливал на него различные операционные системы следующим методом: он создавал новый раздел диска из последовательных секторов, начиная с сектора номер ai и до сектора bi включительно, и устанавливал на него очередную систему. При этом, если очередной раздел хотя бы по одному сектору пересекается с каким-то ранее созданным разделом, то ранее созданный раздел «затирается», и операционная система, которая на него была установлена, больше не может быть загружена.

Напишите программу, которая по информации о том, какие разделы на диске создавал Вася, определит, сколько в итоге работоспособных операционных систем установлено и работает в настоящий момент на Васином компьютере.

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

Сначала вводятся натуральное число M — количество секторов на жестком диске (1 ≤ M ≤ 109) и целое число N — количество разделов, которое последовательно создавал Вася (0 ≤ N ≤ 1000).

Далее идут N пар чисел ai и bi, задающих номера начального и конечного секторов раздела (1 ≤ ai ≤ bi ≤ M).

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

Выведите одно число — количество работающих операционных систем на Васином компьютере.

Пример

input.txt

output.txt

input.txt

output.txt

Решение

7. SNTP

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

Для того чтобы компьютеры поддерживали актуальное время, они могут обращаться к серверам точного времени SNTP (Simple Network Time Protocol). К сожалению, компьютер не может просто получить время у сервера, потому что информация по сети передаётся не мгновенно: пока сообщение с текущим временем дойдёт до компьютера, оно потеряет свою актуальность. Протокол взаимодействия клиента (компьютера, запрашивающего точное время) и сервера (компьютера, выдающего точное время) выглядит следующим образом:

1. Клиент отправляет запрос на сервер и запоминает время отправления A (по клиентскому времени).

2. Сервер получает запрос в момент времени B (по точному серверному времени) и отправляет клиенту сообщение, содержащее время B.

3. Клиент получает ответ на свой запрос в момент времени C (по клиентскому времени) и запоминает его. Теперь клиент, из предположения, что сетевые задержки при передаче сообщений от клиента серверу и от сервера клиенту одинаковы, может определить и установить себе точное время, используя известные значения A, B, C.

Вам предстоит реализовать алгоритм, с точностью до секунды определяющий точное время для установки на клиенте по известным A, B и C. При необходимости округлите результат до целого числа секунд по правилам арифметики (в меньшую сторону, если дробная часть числа меньше 1/2, иначе в большую сторону).

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

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

Программа получает на вход три временные метки A, B, C, по одной в каждой строке. Все временные метки представлены в формате «hh:mm:ss», где «hh» – это часы, «mm» – минуты, «ss» – секунды. Часы, минуты и секунды записываются ровно двумя цифрами каждое (возможно, с дополнительными нулями в начале числа).

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

Программа должна вывести одну временную метку в формате, описанном во входных данных, – вычисленное точное время для установки на клиенте. В выводе не должно быть пробелов, пустых строк в начале вывода.

Пример

input.txt

15:01:00
18:09:45
15:01:40

output.txt

Решение

8. Минимальный прямоугольник

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

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

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

Во входном файле, на первой строке, находится число K (1 ≤ K ≤ 100). На следующих K строках находятся пары чисел Xi и Yi – координаты закрашенных клеток (|Xi|, |Yi| ≤ 109).

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

Выведите в выходной файл координаты левого нижнего и правого верхнего углов прямоугольника.

Примеры

input.txt

output.txt

Решение

9. Сумма в прямоугольнике

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 3 секунды

Ограничение по памяти: 256 мегабайт

Вам необходимо ответить на запросы узнать сумму всех элементов числовой матрицы N×M в прямоугольнике с левым верхним углом (x1, y1) и правым нижним (x2, y2)

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

В первой строке находится числа N, M размеры матрицы (1 ≤ N, M ≤ 1000) и K — количество запросов (1 ≤ K ≤ 100000). Каждая из следующих N строк содержит по M чисел`— элементы соответствующей строки матрицы (по модулю не превосходят 1000). Последующие K строк содержат по 4 целых числа, разделенных пробелом x1 y1 x2 y2 — запрос на сумму элементов матрице в прямоугольнике (1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ M)

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

Для каждого запроса на отдельной строке выведите его результат — сумму всех чисел в элементов матрице в прямоугольнике (x1, y1), (x2, y2)

Пример

input.txt

3 3 2
1 2 3
4 5 6
7 8 9
2 2 3 3
1 1 2 3

output.txt

Решение

10. Скучная лекция

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

Лёша сидел на лекции. Ему было невероятно скучно. Голос лектора казался таким далеким и незаметным…

Чтобы окончательно не уснуть, он взял листок и написал на нём свое любимое слово. Чуть ниже он повторил своё любимое слово, без первой буквы. Ещё ниже он снова написал своё любимое слово, но в этот раз без двух первых и последней буквы.

Тут ему пришла в голову мысль — времени до конца лекции все равно ещё очень много, почему бы не продолжить выписывать всеми возможными способами это слово без какой-то части с начала и какой-то части с конца?

После лекции Лёша рассказал Максу, как замечательно он скоротал время. Максу стало интересно посчитать, сколько букв каждого вида встречается у Лёши в листочке. Но к сожалению, сам листочек куда-то запропастился.

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

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

На вход подаётся строка, состоящая из строчных латинских букв — любимое слово Лёши.
Длина строки лежит в пределах от 5 до 100 000 символов.

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

Для каждой буквы на листочке Лёши, выведите её, а затем через двоеточие и пробел сколько раз она встретилась в выписанных Лёшей словах (см. формат вывода в примерах). Буквы должны следовать в алфавитном порядке. Буквы, не встречающиеся на листочке, выводить не нужно.

Примеры

input.txt

output.txt

input.txt

output.txt

Примечание

Пояснение к первому примеру. Если любимое Лёшино слово — «hello», то на листочке у Лёши будут выписаны следующие слова:

«hello»

«hell»

«ello»

«hel»

«ell»

«llo»

«he»

«el»

«ll»

«lo»

«h»

«e»

«l»

«l»

«o»

Среди этих слов 8 раз встречается буква «e», 5 раз — буква «h», 17 раз — буква «l» и 5 раз буква «o».

Решение

11. Стек с защитой от ошибок

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

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

push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.

pop
Удалить из стека последний элемент. Программа должна вывести его значение.

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

size
Программа должна вывести количество элементов в стеке.

clear
Программа должна очистить стек и вывести ok.

exit
Программа должна вывести bye и завершить работу.

Перед исполнением операций back и pop программа должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.

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

Вводятся команды управления стеком, по одной на строке

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

Программа должна вывести протокол работы стека, по одному сообщению на строке

Примеры

input.txt

output.txt

input.txt

size
push 1
size
push 2
size
push 3
size
exit

output.txt

input.txt

push 3
push 14
size
clear
push 1
back
push 2
back
pop
size
pop
size
exit

output.txt

ok
ok
2
ok
ok
1
ok
2
2
1
1
0
bye

Решение

12. Правильная скобочная последовательность

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа дожна определить, является ли данная скобочная последовательность правильной. Пустая последовательность явлется правильной. Если A – правильная, то последовательности (A), [A], {A} – правильные. Если A и B – правильные последовательности, то последовательность AB – правильная.

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

В единственной строке записана скобочная последовательность, содержащая не более 100000 скобок.

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

Если данная последовательность правильная, то программа должна вывести строку yes, иначе строку no.

Примеры

input.txt

output.txt

input.txt

output.txt

input.txt

output.txt

Решение

13. Постфиксная запись

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D * обозначает привычное нам (B + C) * D, а запись A B C + D * + означает A + (B + C) * D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения.

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

В единственной строке записано выражение в постфиксной записи, содержащее цифры и операции +, -, *. Цифры и операции разделяются пробелами. В конце строки может быть произвольное количество пробелов.

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

Необходимо вывести значение записанного выражения.

Пример

input.txt

output.txt

Решение

14. Сортировка вагонов lite

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

https://contest.yandex.ru/testsys/statement-image?imageId=6b47dd0f62b0e9704864ecb0be7b66943d3c0afd847bde6b2a7138ce61337b35

Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.

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

Вводится число N — количество вагонов в поезде (1 ≤ N ≤ 100). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.

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

Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO.

Примеры

input.txt

output.txt

input.txt

output.txt

input.txt

output.txt

Решение

15. Великое Лайнландское переселение

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Лайнландия представляет из себя одномерный мир, являющийся прямой, на котором располагаются N городов, последовательно пронумерованных от 0 до N — 1 . Направление в сторону от первого города к нулевому названо западным, а в обратную — восточным.
Когда в Лайнландии неожиданно начался кризис, все были жители мира стали испытывать глубокое смятение. По всей Лайнландии стали ходить слухи, что на востоке живётся лучше, чем на западе.
Так и началось Великое Лайнландское переселение. Обитатели мира целыми городами отправились на восток, покинув родные улицы, и двигались до тех пор, пока не приходили в город, в котором средняя цена проживания была меньше, чем в родном.

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

В первой строке дано одно число N (2≤N≤10^5) — количество городов в Лайнландии. Во второй строке дано N чисел
ai (0≤ai≤10^9) — средняя цена проживания в городах с нулевого по (N — 1)-ый соответственно.

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

Для каждого города в порядке с нулевого по (N — 1)-ый выведите номер города, в который переселятся его изначальные жители. Если жители города не остановятся в каком-либо другом городе, отправившись в Восточное Бесконечное Ничто, выведите -1 .

Примеры

input.txt

output.txt

Решение

16. Очередь с защитой от ошибок

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

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

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

Возможные команды для программы:

push n
Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.

pop
Удалить из очереди первый элемент. Программа должна вывести его значение.

front
Программа должна вывести значение первого элемента, не удаляя его из очереди.

size
Программа должна вывести количество элементов в очереди.

clear
Программа должна очистить очередь и вывести ok.

exit
Программа должна вывести bye и завершить работу.

Перед исполнением операций front и pop программа должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.

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

Вводятся команды управления очередью, по одной на строке

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

Требуется вывести протокол работы очереди, по одному сообщению на строке

Пример

input.txt

output.txt

input.txt

size
push 1
size
push 2
size
push 3
size
exit

output.txt

input.txt

push 3
push 14
size
clear
push 1
front
push 2
front
pop
size
pop
size
exit

output.txt

ok
ok
2
ok
ok
1
ok
1
1
1
2
0
bye

Решение

17. Игра в пьяницу

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайта

В игре в пьяницу карточная колода раздается поровну двум игрокам. Далее они вскрывают по одной верхней карте, и тот, чья карта старше, забирает себе обе вскрытые карты, которые кладутся под низ его колоды. Тот, кто остается без карт – проигрывает. Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту («шестерка берет туза»). Игрок, который забирает себе карты, сначала кладет под низ своей колоды карту первого игрока, затем карту второго игрока (то есть карта второго игрока оказывается внизу колоды). Напишите программу, которая моделирует игру в пьяницу и определяет, кто выигрывает. В игре участвует 10 карт, имеющих значения от 0 до 9, большая карта побеждает меньшую, карта со значением 0 побеждает карту 9.

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

Программа получает на вход две строки: первая строка содержит 5 чисел, разделенных пробелами — номера карт первого игрока, вторая – аналогично 5 карт второго игрока. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.

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

Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 106 ходов игра не заканчивается, программа должна вывести слово botva.

Примеры

input.txt

output.txt

input.txt

output.txt

input.txt

output.txt

Решение

18. Дек с защитой от ошибок

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунды

Ограничение по памяти: 64 мегабайт

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

Возможные команды для программы:

push_front n
Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back n
Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back
Извлечь из дека последний элемент. Программа должна вывести его значение.

front
Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back
Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size
Вывести количество элементов в деке.

clear
Очистить дек (удалить из него все элементы) и вывести ok.

exit
Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Перед исполнением операций pop_front, pop_back, front, back программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_front, pop_back, front, back, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.

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

Вводятся команды управления деком, по одной на строке.

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

Требуется вывести протокол работы дека, по одному сообщению на строке

Пример

input.txt

output.txt

input.txt

size
push_back 1
size
push_back 2
size
push_front 3
size
exit

output.txt

input.txt

push_back 3
push_front 14
size
clear
push_front 1
back
push_back 2
front
pop_back
size
pop_front
size
exit

output.txt

ok
ok
2
ok
ok
1
ok
1
2
1
1
0
bye

Решение

19. Хипуй

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 2 секунды

Ограничение по памяти: 64 мегабайт

В этой задаче вам необходимо самостоятельно (не используя соответствующие классы и функции стандартной библиотеки) организовать структуру данных Heap для хранения целых чисел, над которой определены следующие операции: a) Insert(k) – добавить в Heap число k ; b) Extract достать из Heap наибольшее число (удалив его при этом).

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

В первой строке содержится количество команд N (1 ≤ N ≤ 100000), далее следуют N команд, каждая в своей строке. Команда может иметь формат: “0 <число>” или “1”, обозначающий, соответственно, операции Insert(<число>) и Extract. Гарантируется, что при выполнении команды Extract в структуре находится по крайней мере один элемент.

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

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

Пример

input.txt

output.txt

input.txt

14
0 1
0 345
1
0 4346
1
0 2435
1
0 235
0 5
0 365
1
1
1
1

output.txt

345
4346
2435
365
235
5
1

Решение

20. Пирамидальная сортировка

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 2 секунды

Ограничение по памяти: 64 мегабайт

Отсортируйте данный массив. Используйте пирамидальную сортировку.

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

Первая строка входных данных содержит количество элементов в массиве N, N ≤ 105. Далее задаются N целых чисел, не превосходящих по абсолютной величине 109.

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

Выведите эти числа в порядке неубывания.

Примеры

input.txt

output.txt

input.txt

output.txt

Решение

21. Три единицы подряд

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 3 секунды

Ограничение по памяти: 256 мегабайт

По данному числу N определите количество последовательностей из нулей и единиц длины N, в которых никакие три единицы не стоят рядом.

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

Во входном файле написано натуральное число N, не превосходящее 35.

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

Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 2^31-1.

Пример

input.txt

output.txt

Решение

22. Кузнечик

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

У одного из студентов в комнате живёт кузнечик, который очень любит прыгать по клетчатой одномерной доске. Длина доски — N клеток. К его сожалению, он умеет прыгать только на 1, 2, …, k клеток вперёд.

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

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

В первой и единственной строке входного файла записано два целых числа — N и k.
1≤N≤30, 1≤k≤10

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

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

Примеры

input.txt

output.txt

Решение

23. Калькулятор

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Имеется калькулятор, который выполняет следующие операции:

умножить число X на 2;
умножить число X на 3;
прибавить к числу X единицу.
Определите, какое наименьшее количество операций требуется, чтобы получить из числа 1 число N.

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

Во входном файле написано натуральное число N, не превосходящее 10^6.

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

В первой строке выходного файла выведите минимальное количество операций. Во второй строке выведите числа, последовательно получающиеся при выполнении операций. Первое из них должно быть равно 1, а последнее N. Если решений несколько, выведите любое.

Примеры

input.txt

output.txt

input.txt

output.txt

Решение

24. Покупка билетов

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя «постояльцев» очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.

Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.

Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов — Bi секунд, трех билетов — Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.

Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).

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

На вход программы поступает сначала число N — количество покупателей в очереди (1 ≤ N ≤ 5000). Далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы.

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

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

Примеры

input.txt

5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1

output.txt

Решение

25. Гвоздики

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

В дощечке в один ряд вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.

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

В первой строке входных данных записано число N — количество гвоздиков (2 ≤ N ≤ 100). В следующей строке заданы N чисел — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

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

Выведите единственное число — минимальную суммарную длину всех ниточек.

Пример

input.txt

output.txt

Решение

26. Самый дешевый путь

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

В каждой клетке прямоугольной таблицы
N × M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).
Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.

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

Вводятся два числа N и M — размеры таблицы (
1≤N≤20, 1≤M≤20). Затем идет N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).

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

Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.

Примеры

input.txt

5 5
1 1 1 1 1
3 100 100 100 100
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1

output.txt

Решение

27. Вывести маршрут максимальной стоимости

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

В левом верхнем углу прямоугольной таблицы размером
N × M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.
Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). Найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.

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

В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

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

Первая строка выходных данных содержит максимальную возможную сумму, вторая — маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Примеры

input.txt

5 5
9 9 9 9 9
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9

output.txt

Решение

28. Ход конём

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. В данной задаче конь может перемещаться на две клетки вниз и одну клетку вправо или на одну клетку вниз и две клетки вправо.

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

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

Входной файл содержит два натуральных числа N и M (1≤N, M≤50).

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

В выходной файл выведите единственное число — количество способов добраться конём до правого нижнего угла доски.

Пример

input.txt

output.txt

input.txt

output.txt

Решение

29. Кафе

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайта

Около Петиного университета недавно открылось новое кафе, в котором действует следующая система скидок: при каждой покупке более чем на 100 рублей покупатель получает купон, дающий право на один бесплатный обед (при покупке на сумму 100 рублей и меньше такой купон покупатель не получает).

Однажды Пете на глаза попался прейскурант на ближайшие N дней. Внимательно его изучив, он решил, что будет обедать в этом кафе все N дней, причем каждый день он будет покупать в кафе ровно один обед. Однако стипендия у Пети небольшая, и поэтому он хочет по максимуму использовать предоставляемую систему скидок так, чтобы его суммарные затраты были минимальны. Требуется найти минимально возможную суммарную стоимость обедов и номера дней, в которые Пете следует воспользоваться купонами.

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

В первой строке входного файла записано целое число N (0 ≤ N ≤ 100). В каждой из последующих N строк записано одно целое число, обозначающее стоимость обеда в рублях на соответствующий день. Стоимость — неотрицательное целое число, не превосходящее 300.

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

В первой строке выдайте минимальную возможную суммарную стоимость обедов. Во второй строке выдайте два числа K1 и K2 — количество купонов, которые останутся неиспользованными у Пети после этих N дней и количество использованных им купонов соответственно.

В последующих K2 строках выдайте в возрастающем порядке номера дней, когда Пете следует воспользоваться купонами. Если существует несколько решений с минимальной суммарной стоимостью, то выдайте то из них, в котором значение K1 максимально (на случай, если Петя когда-нибудь ещё решит заглянуть в это кафе). Если таких решений несколько, выведите любое из них.

Примеры

input.txt

output.txt

Решение

30. НОП с восстановлением ответа

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунды

Ограничение по памяти: 64 мегабайт

Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.

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

В первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

В третьей строке записано число M – длина второй последовательности (1 ≤ M ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

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

Требуется вывести наибольшую общую подпоследовательность данных последовательностей, через пробел.

Пример

input.txt

output.txt

input.txt

output.txt

Решение

31. Поиск в глубину

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 2 секунда

Ограничение по памяти: 256 мегабайт

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

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

В первой строке записаны два целых числа N (1 ≤ N ≤ 103) и M (0 ≤ M ≤ 5 * 105) — количество вершин и ребер в графе. В последующих M строках перечислены ребра — пары чисел, определяющие номера вершин, которые соединяют ребра.

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

В первую строку выходного файла выведите число K — количество вершин в компоненте связности. Во вторую строку выведите K целых чисел — вершины компоненты связности, перечисленные в порядке возрастания номеров.

Пример

input.txt

output.txt

Решение

32. Компоненты связности

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Дан неориентированный невзвешенный граф, состоящий из N вершин и M ребер. Необходимо посчитать количество его компонент связности и вывести их.

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

Во входном файле записано два числа N и M (0 < N ≤ 100000, 0 ≤ M ≤ 100000). В следующих M строках записаны по два числа i и j (1 ≤ i, j ≤ N), которые означают, что вершины i и j соединены ребром.

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

В первой строчке выходного файла выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй — сами вершины в произвольном порядке.

Примеры

input.txt

output.txt

input.txt

output.txt

Решение

33. Списывание

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Во время контрольной работы профессор Флойд заметил, что некоторые студенты обмениваются записками. Сначала он хотел поставить им всем двойки, но в тот день профессор был добрым, а потому решил разделить студентов на две группы: списывающих и дающих списывать, и поставить двойки только первым.

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

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

В первой строке находятся два числа N и M — количество студентов и количество пар студентов, обменивающихся записками (1 ≤ N ≤ 102, 0 ≤ M ≤ N(N−1)/2).

Далее в M строках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 1). Каждая пара студентов перечислена не более одного раза.

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

Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы — выведите YES; иначе выведите NO.

Пример

input.txt

output.txt

input.txt

output.txt

Решение

34. Топологическая сортировка

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Дан ориентированный граф. Необходимо построить топологическую сортировку.

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

В первой строке входного файла два натуральных числа N и M (1 ≤ N, M ≤ 100 000) — количество вершин и рёбер в графе соответственно. Далее в M строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.

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

Выведите любую топологическую сортировку графа в виде последовательности номеров вершин (перестановка чисел от 1 до N). Если топологическую сортировку графа построить невозможно, выведите -1.

Примеры

input.txt

6 6
1 2
3 2
4 2
2 5
6 5
4 6

output.txt

Решение

35. Поиск цикла

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Дан неориентированный граф. Требуется определить, есть ли в нем цикл, и, если есть, вывести его.

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

В первой строке дано одно число n — количество вершин в графе ( 1 ≤ n ≤ 500 ). Далее в n строках задан сам граф матрицей смежности.

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

Если в иcходном графе нет цикла, то выведите «NO». Иначе, в первой строке выведите «YES», во второй строке выведите число k — количество вершин в цикле, а в третьей строке выведите k различных чисел — номера вершин, которые принадлежат циклу в порядке обхода (обход можно начинать с любой вершины цикла). Если циклов несколько, то выведите любой.

Примеры

input.txt

output.txt

input.txt

4
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0

output.txt

input.txt

5
0 1 0 0 0
1 0 0 0 0
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0

output.txt

Решение

36. Длина кратчайшего пути

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

В неориентированном графе требуется найти длину минимального пути между двумя вершинами.

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

Первым на вход поступает число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.

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

Выведите L – длину кратчайшего пути (количество ребер, которые нужно пройти).
Если пути нет, нужно вывести -1.

Примеры

input.txt

10
0 1 0 0 0 0 0 0 0 0
1 0 0 1 1 0 1 0 0 0
0 0 0 0 1 0 0 0 1 0
0 1 0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 1
0 1 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 1 1 0 0 0 0
5 4

output.txt

input.txt

5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5

output.txt

Решение

37. Путь в графе

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

В неориентированном графе требуется найти минимальный путь между двумя вершинами.

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

Первым на вход поступает число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.

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

Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину.

Необходимо вывести путь (номера всех вершин в правильном порядке). Если пути нет, нужно вывести -1.

Пример

input.txt

10
0 1 0 0 0 0 0 0 0 0
1 0 0 1 1 0 1 0 0 0
0 0 0 0 1 0 0 0 1 0
0 1 0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 1
0 1 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 1 1 0 0 0 0
5 4

output.txt

Решение

38. Блохи

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

На клеточном поле, размером NxM (2 ≤ N, M ≤ 250) сидит Q (0 ≤ Q ≤ 10000) блох в различных клетках. «Прием пищи» блохами возможен только в кормушке — одна из клеток поля, заранее известная. Блохи перемещаются по полю странным образом, а именно, прыжками, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждой блохи до кормушки определяется как количество прыжков. Определить минимальное значение суммы длин путей блох до кормушки или, если собраться блохам у кормушки невозможно, то сообщить об этом. Сбор невозможен, если хотя бы одна из блох не может попасть к кормушке.

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

В первой строке входного файла находится 5 чисел, разделенных пробелом: N, M, S, T, Q. N, M — размеры доски (отсчет начинается с 1); S, T — координаты клетки — кормушки (номер строки и столбца соответственно), Q — количество блох на доске. И далее Q строк по два числа — координаты каждой блохи.

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

Содержит одно число — минимальное значение суммы длин путей или -1, если сбор невозможен.

Примеры

input.txt

output.txt

input.txt

4 4 1 1 16
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

output.txt

Решение

39. Путь спелеолога

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

Пещера представлена кубом, разбитым на N частей по каждому измерению (то есть на N3 кубических клеток). Каждая клетка может быть или пустой, или полностью заполненной камнем. Исходя из положения спелеолога в пещере, требуется найти, какое минимальное количество перемещений по клеткам ему требуется, чтобы выбраться на поверхность. Переходить из клетки в клетку можно, только если они обе свободны и имеют общую грань.

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

В первой строке содержится число N (1 ≤ N ≤ 30). Далее следует N блоков. Блок состоит из пустой строки и N строк по N символов: # — обозначает клетку, заполненную камнями, точка — свободную клетку. Начальное положение спелеолога обозначено заглавной буквой S. Первый блок представляет верхний уровень пещеры, достижение любой свободной его клетки означает выход на поверхность. Выход на поверхность всегда возможен.

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

Вывести одно число — длину пути до поверхности.

Примеры

input.txt

3

###
###
.##

.#.
.#S
.#.

###
...
###

output.txt

Примечание

Нужно спуститься на уровень вниз, сделать два движения на запад, подняться на уровень вверх, сделать движение на юг, подняться на уровень вверх.

Решение

40. Метро

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться со станции A на станцию B. Если данный метрополитен не соединяет все линии в одну систему, то может так получиться, что со станции A на станцию B добраться невозможно, в этом случае ваша программа должна это определить.

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

Сначала вводится число N — количество станций метро в городе (2≤N≤100). Далее следует число M — количество линий метро (1≤M≤20). Далее идет описание M линий. Описание каждой линии состоит из числа Pi — количество станций на этой линии (2≤Pi≤50) и Pi чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

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

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

Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции A на станцию B невозможно, программа должна вывести одно число –1 (минус один).

Пример

input.txt

output.txt

Решение