Стек (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)

A: Стек с защитой от ошибок

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

Перед исполнением операций back и pop программа должна проверять, содержится ли в стеке хотя бы один элемент. Время работы каждой операции O(1).

size push 1 size push 2 size push 3 size exit
0 ok 1 ok 2 ok 3 bye
IDE

B: Ближайший больший справа

Дана последовательность $A_0, A_1, \dots, A_{n-1}$ из $n$ целых чисел. Для каждого числа $A_i$ найдите наименьшее $j$ такое, что $j>i$ и $A_j>A_i$.
В первой строке входного файла записано натуральное число $n~(n < 5\cdot10^4)$. В следующей строке через пробел записаны целые числа $A_0, A_1, \dots, A_{n-1}$.
Требуется вывести $n$ чисел в одной строке через пробел. Для каждого $i~(0\leqslant i\leqslant n-1)$ вывести соответствующее $j$. Если правее $A_i$ нет чисел, больших его, в качестве ответа выведите число $-1$.
Время $O(n)$, дополнительная память $O(n)$.

5 1 3 2 4 5
1 3 3 4 -1
IDE

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

С клавиатуры вводится строка — скобочное выражение, содержащее три вида скобок: ()[]{}.
Программа дожна определить, является ли данная скобочная последовательность правильной.
В единственной строке входного файла записана скобочная последовательность, содержащая не более $100000$ скобок.
Если данная скобочная последовательность правильная, то программа должна вывести строку YES, иначе строку NO.

()[]
YES
][
NO
IDE

D: Удаление скобок

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

())(()
2
))(((
5
IDE

E: Постфиксная запись

В постфиксной записи (или обратной польской записи) операция записывается после двух операндов.
Термин получил название благодаря польскому логику Яну Лукасевичу, придумавшему обычную, т.е. префиксную запись формул (операция предшествует записи операндов).
Обратная польская запись (RPN — Reverse Polish Notation) появилась примерно в середине 50-х — начале 60-х годов благодаря работам сразу нескольких учёных (Burks, Warren, Wright, позже — Bauer, Dijkstra).
Ниже приведены примеры выражений в обычной и постфиксной формах:

ОбычнаяПостфиксная
A + B A B +
(B + C) * D B C + D *
A + (B + C) * D A B C + D * +

Такой способ записи позволяет избавиться от скобок и вычислять значение алгебраического выражения при помощи стека, не занимаясь его синтаксическим разбором. Выражение обрабатывается слева направо. Числа кладутся в стек, а операции выполняются с верхними двумя элементами стека, вместо которых в стек помещается результат этой операции. Нужно обратить внимание на некоммутативные операции (вычитание и деление).
В единственной строке записано корректное выражение в постфиксной записи, содержащее однозначные числа и операции $+, -, *$, разделённые пробелами.
Необходимо вывести значение записанного выражения.

8 9 + 1 7 - *
-102
IDE

F: Шарики

В одной компьютерной игре игрок выставляет в линию шарики разных цветов. Когда образуется непрерывная цепочка из трёх и более шариков одного цвета, она удаляется из линии. Все шарики при этом сдвигаются друг к другу, и ситуация может повториться.
Напишите программу, которая по данной ситуации определяет, сколько шариков будет сейчас "уничтожено". Непрерывных цепочек из трех и более одноцветных шаров в начальный момент может быть не более одной.
Сначала вводится число $N~(1\leqslant N\leqslant 3\cdot 10^5)$ — количество шариков в цепочке, а в следующей строке цвета шариков (числа от $0$ до $9$, каждому цвету соответствует своё целое число).
Требуется вывести количество шариков, которое будет "уничтожено".

6 5 1 3 3 3 2
3
IDE

G: Сортировка вагонов

К тупику со стороны пути $1$ (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути $2$. Затем можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути $2$. И так далее (так, что каждый вагон может лишь один раз заехать с пути $1$ в тупик, а затем один раз выехать из тупика на путь $2$). Заезжать в тупик с пути $2$ или выезжать из тупика на путь $1$ запрещается. Нельзя с пути $1$ попасть на путь $2$, не заезжая в тупик.
Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути $2$ в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.
В первой строке вводится число $N$ — количество вагонов в поезде $(1\leqslant N\leqslant10^5)$. Во второй строке перечислены номера вагонов в порядке от головы поезда, едущего по пути $1$ в сторону тупика. Вагоны пронумерованы натуральными числами от $1$ до $N$, каждое из которых встречается ровно один раз.
Если можно сделать так, чтобы вагоны шли в порядке от $1$ до $N$, считая от головы поезда, когда поезд поедет по пути $2$ из тупика, выведите слово YES, иначе выведите NO.

3 3 2 1
YES
Надо весь поезд завезти в тупик, а затем целиком вывезти его на 2-й путь.
4 4 1 3 2
YES
Сначала надо в тупик завезти два вагона, один из которых оставить в тупике, а второй — вывезти на $2$-й путь, после чего завезти в тупик еще два вагона и вывезти $3$ вагона, стоящие в тупике, на $2$-й путь.
3 2 3 1
NO
IDE

H: Баржа

На барже располагается $K$ грузовых отсеков. В каждый отсек можно поместить некоторое количество бочек с одним из $10000$ видов топлива. Причём извлечь бочку из отсека можно лишь в случае, если все бочки, помещённые в этот отсек после неё, уже были извлечены. Таким образом в каждый момент времени в каждом непустом отсеке имеется ровно одна бочка, которую можно извлечь не трогая остальных. Будем называть такие бочки крайними.
В начале баржа пуста. Затем она последовательно проплывает через $N$ доков, причём в каждом доке на баржу либо погружается бочка с некоторым видом топлива в некоторый отсек, либо выгружается крайняя бочка из некоторого отсека. Однако, если указанный отсек пуст, либо если выгруженная бочка содержит не тот вид топлива, который ожидалось, следует зафиксировать ошибку. Если на баржу оказывается погружено более $P$ бочек или если после прохождения всех доков она не стала пуста, следует также зафиксировать ошибку. От вас требуется либо указать максимальное количество бочек, которые одновременно пребывали на барже либо зафиксировать ошибку.
В первой строке три целых числа $N,K$ и $P~(1\leqslant N,K,P\leqslant100000)$. Далее следует $N$ строк с описанием действия, выполняемого в очередном доке. Если в нём происходит погрузка, то строка имеет вид + A B, где $A$ — номер отсека, в который помещается бочка, а $B$ — номер вида топлива в ней. Если же док занимается разгрузкой, то строка имеет вид - A B, где $A$ — номер отсека, из которого извлекается бочка, а $B$ — номер ожидаемого вида топлива.
Вывести либо одно число, равное искомому максимуму в случае безошибочного прохождения баржой маршрута, либо вывести слово Error в противном случае.

6 1 2 + 1 1 + 1 2 - 1 2 - 1 1 + 1 3 - 1 3
2
IDE

I: Контейнеры

На складе хранятся контейнеры с товарами $N$ различных видов. Все контейнеры составлены в $N$ стопок. В каждой стопке могут находиться товары любых видов. Стопка может быть первоначально пустой.
Автопогрузчик может взять верхний контейнер из любой стопки и поставить его сверху в любую стопку. Необходимо расставить все контейнеры с товаром первого вида в первую стопку, второго — во вторую и т.д.
В первой строке входных данных записано одно натуральное число $N$, не превосходящее $500$.
В следующих $N$ строках описаны стопки контейнеров: сначала записано число $k_i$ — количество контейнеров в $i$-й стопке, а затем $k_i$ чисел — виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более $500$ контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).
Программа должна вывести описание действий автопогрузчика: для каждого действия напечатать два числа – из какой стопки брать контейнер и в какую стопку класть. Обратите внимание, что минимизировать количество операций автопогрузчика не требуется. Если задача не имеет решения, необходимо вывести одно число $0$. Если контейнеры изначально правильно размещены по стопкам, то выводить ничего не нужно.

3 4 1 2 3 2 0 0
1 2 1 3 1 2
В первой стопке лежат четыре контейнера — снизу контейнер с товаром первого вида, над ним — с товаром второго вида, над ним третьего, и сверху еще один контейнер с товаром второго вида. Вторая и третья стопки — пусты.
IDE

J: Гемоглобин

Каждый день к Грегори Хаусу приходит много больных, и у каждого измеряется уровень гемоглобина в крови. Данные по всем пациентам заносятся в базу данных. Но волчанка попадается один раз на миллион, а работать с остальными неинтересно. Чтобы Хаус не выгонял больных, Кадди иногда запрашивает статистику по $k$ последним больным: ей хочется знать сумму их уровня гемоглобина. Также Хаус — мизантроп: он смотрит уровень гемоглобина больного, который поступил к нему позже всех, и, видя, что это точно не волчанка, выписывает его из больницы и удаляет информацию о нем из базы.
Автоматизацию процесса Хаус поручил Чейзу. Но Чейз почему-то не справился с этой задачей и попросил вас ему помочь.
В первой строке входного файла задано число $n~(1\leqslant n\leqslant100000)$ — число обращений к базе данных. Запросы к базе выглядят следующим образом: +x $(1\leqslant x\leqslant10^9)$ — добавить пациента с уровнем гемоглобина $x$ в базу, знак «-» — удалить последнего пациента из базы, ?k $(1\leqslant k\leqslant10^5)$ — вывести суммарный гемоглобин последних $k$ пациентов. Гарантируется, что $k$ не превосходит число элементов в базе. Также гарантируется, что запросов на удаление к пустой базе не поступает. Перед началом работы база данных пуста.
Для каждого запроса «-» вывести уровень гемоглобина в крови пациента, а для каждого запроса ?k — суммарный гемоглобин у последних $k$ оставшихся пациентов. Ответы выводите в порядке поступления запросов.

7 +1 +2 +3 ?2 - - ?1
5 3 2 1
IDE

K: Гистограмма

Гистограмма — многоугольник, сформированный из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая состоит из прямоугольников с высотами $2,1,4,5,1,3,3$. Все прямоугольники на этом рисунке имеют ширину, равную $1$.
Вычислите максимальную площадь прямоугольника в гистограмме, который находится на общей базовой линии. На рисунке справа заштрихованная фигура является самым большим выровненным прямоугольником на изображенной гистограмме.
В первой строке входного файла записано число $N~(0\leqslant N\leqslant10^6)$ — количество прямоугольников гистограммы. Затем следует $N$ целых чисел $h1,\dots, h_n$, где $0\leqslant h_i\leqslant10^9$. Эти числа обозначают высоты прямоугольников гистограммы слева направо. Ширина каждого прямоугольника равна~$1$.
Выведите площадь самого большого прямоугольника в гистограмме. Помните, что этот прямоугольник должен быть на общей базовой линии.

7 2 1 4 5 1 3 3
8
IDE

Очередь (queue)

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

L: Реализация очереди

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

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит $100$, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.
Время работы каждой операции O(1), т.е. не должно зависеть от размера очереди.
Размер массива, в котором хранятся элементы очереди должен быть фиксирован при создании очереди и не меняться во время выполнения программы.

size push 1 size push 2 size push 3 size exit
0 ok 1 ok 2 ok 3 bye
Подсказка

Для представления очереди удобно хранить следующие параметры: массив, в котором хранятся элементы очереди, индекс элемента-головы (head), текущее количество элементов в очереди (size) и максимальное количество элементов в очереди (length — фактически это размер массива).

IDE

M: Реализация очереди неограниченного размера с защитой от ошибок

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

Размер очереди в момент создания должен быть равен $0$. При добавлении элемента в случае, если очередь полна, необходимо увеличивать размер массива для хранения элементов очереди. Используйте следующую формулу для новой длины списка (именно она используется в реализации списки в питоне):
new_size = old_size + old_size // 8 + (3 if old_size < 9 else 6)
(или new_size = old_size + (old_size >> 3) + (old_size < 9 ? 3 : 6) в С++).
Перед исполнением операций front и pop программа должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error. Время работы каждой операции (в среднем) O(1), т.е. не должно зависеть от размера очереди.

push 1 front exit
ok 1 bye
size push 1 size push 2 size push 3 size exit
0 ok 1 ok 2 ok 3 bye
IDE

N: Игра в пьяницу

В игре в пьяницу карточная колода раздается поровну двум игрокам. Далее они вскрывают по одной верхней карте, и тот, чья карта старше, забирает себе обе вскрытые карты, которые кладутся под низ его колоды. Тот, кто остается без карт — проигрывает.
Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту ("шестерка берет туза").
Игрок, который забирает себе карты, сначала кладет под низ своей колоды карту первого игрока, затем карту второго игрока (то есть карта второго игрока оказывается внизу колоды).
Напишите программу, которая моделирует игру в пьяницу и определяет, кто выигрывает. В игре участвует $10$ карт, имеющих значения от $0$ до $9$, большая карта побеждает меньшую, карта со значением $0$ побеждает карту $9$ (и только её).
Программа получает на вход две строки: первая строка содержит $5$ чисел, разделенных пробелами — номера карт первого игрока, вторая – аналогично $5$ карт второго игрока. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении $10^6$ ходов игра не заканчивается, программа должна вывести слово tie.

1 3 5 7 9 2 4 6 8 0
second 5
IDE

Дек (deque)

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

O: Реализация дека

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

Гарантируется, что количество элементов в деке в любой момент не превосходит $10^5$. Все операции pop_front, pop_back, front, back всегда корректны. Время на выполнение каждой операции должно быть $O(1)$, то есть не зависеть от количества элементов в деке.
Программе на вход подаются команды управления деком, по одной на строке.
Требуется вывести протокол работы дека, по одному сообщению на строке.

size push_back 1 size push_back 2 size push_front 3 size exit
0 ok 1 ok 2 ok 3 bye
IDE

P: Минимум в окошке

Дан массив целых чисел размера $N$ и натуральное число $k$ — размер «окошка», в котором видно ровно $k$ соседних элементов массива. «Окошко» двигается от крайнего левого положения (совпадают левый край массива и левый край "окошка") до крайнего правого положения (совпадают правый край массива и правый край окошка) — всего $N-k+1$ позиций.
Требуется написать программу, выводящую значение минимума для всех последовательных положений «окошка». Время работы линейно зависит от $N$ и не зависит от $k$.
В первой строке входных данных содержатся два числа $N$ и $K~(1\leqslant N\leqslant150000, 1\leqslant K\leqslant10000, K\leqslant N)$ — длины последовательности и «окна», соответственно. На следующей строке находятся $N$ чисел — сама последовательность.
Выходные данные должны содержать $N-K+1$ строк — минимумы для каждого положения окна.

7 3 1 3 2 4 5 3 1
1 2 2 3 1
Подсказка
Да что-то непонятное тут требуют...

Рассмотрите дек, в клотором хранятся пары <значение, индекс>. Инвариант: с правой стороны дека всегда находится текущий ответ, а внутри — только числа, которые могут стать ответом. Далее, перебирая элементы массива слева направо, требуется обновить состояние дека. В частности — рассмотреть случаи, когда текущий элемент меньше элемента с правого конца дека, меньше/больше элемента с правого конца дека.

IDE

Q: Реклама

Фирма NNN решила транслировать свой рекламный ролик в супермаркете XXX. Однако денег, запланированных на рекламную кампанию, хватило лишь на две трансляции ролика в течение одного рабочего дня. И при этом обязательно транслировать ровно два рекламных ролика в день.
Фирма собрала информацию о количестве покупателей в каждый момент некоторого дня. Менеджер по рекламе предположил, что и на следующий день покупатели будут приходить и уходить ровно в те же моменты времени.
Помогите ему определить моменты времени, когда нужно включить трансляцию рекламных роликов, чтобы как можно большее количество покупателей прослушало ролик.
Ролик длится ровно одну единицу времени. Для каждого момента времени известно количество покупателей, находящихся в магазине в этот момент. Между концом первой рекламы и началом следующей должна пройти как минимум $K-1$ единица времени.
Первая строка содержит два числа $N$ (моментов времени) и $K$ (время совершения покупки одним покупателем). Гарантируется, что $N>K~(N,K\leqslant200000)$. Во второй строке содержится $N$ чисел $a_i$ — количество покупателей в момент времени $i~(0\leqslant a_i\leqslant2\cdot10^9)$.
Выведите единственное число — количество просмотревших рекламу покупателей.

5 2 3 5 1 4 2
9
IDE

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

R: Обратная польская запись — 1

Дано арифметическое выражение с целыми числами и арифметическими операциями +, -, *, /, // (без скобок). Преобразуйте его в обратную польскую запись.

3 + 4
3 4 +
-1 + 4 * 2 * 4 - 3 // 2
-1 4 2 4 * * 3 2 // - +
IDE

S: Обратная польская запись — 2

Дано арифметическое выражение с целыми числами, арифметическими операциями +, -, *, /, // ,** ,% и скобками. Преобразуйте его в обратную польскую запись.

Приоритет операций в порядке убывания:

ОперацияОписание
(...)Выражение в скобках;
**Возведение в степень;
~ + -Комплиментарный оператор;
* / % //Умножение, деление, деление по модулю, целочисленное деление;
+ -Сложение и вычитание;
>> <<Побитовый сдвиг вправо и побитовый сдвиг влево;
&Бинарный "И";
^ |Бинарный "Исключительное ИЛИ" и бинарный "ИЛИ";
<= < > >=Операторы сравнения;
<> == !=Операторы равенства;
= %= /= //= -= += *= **=Операторы присваивания;
is, is notТождественные операторы;
in, not inОператоры членства;
not, or, andЛогические операторы;
3 + 4 * 2 / (1 - 5) ** 2 - 3 % 2
3 4 2 * 1 5 - 2 ** / + 3 2 % -
IDE

ZA: Игры со строками

Во время игры в Scrabble Дуня любит играть со своими буквами, перебирая их и меняя в задумчивости местами. Буквы стоят на специальной подставке, для каждой буквы предусмотрено отдельная позиция. Все позиции пронумерованы от $0$ до $N-1$, где $N$ — количество букв.
Вам дана строка и целое неотрицательное число $K$, имеющее следующий смысл: после того, как Дуня поменяла порядок некоторых букв из первоначальной строки, известно, что каждая буква изменила свою позицию не более, чем на $K$.
Требуется по входным данным вывести лексикографически минимальную строку, которая могла получиться при указанных ограничениях.

ABRACADABRA 2
AABARACBDAR
IDE