--->
35 задач
<---
Источники
#1656
Темы:
[Стек]
[Дерево отрезков, RSQ, RMQ]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Региональный этап,
Кировская открытая областная олимпиада,
2005,
Задача E
]
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes
Дана последовательность N прямоугольников различной ширины и высоты (wi,hi). Прямоугольники расположены, начиная с точки (0, 0), на оси ОХ вплотную друг за другом (вправо). Требуется найти M - площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.
Формат входных данных
В первой строке задано число N (1 ≤ N ≤ 8000). Далее идет N строк. В каждой строке содержится два числа: ширина и высота i-го прямоугольника. Значение 
, 0 < hi ≤ 3*104.
Формат выходных данных
Вывести одно число М. Значение M не превосходит 2*109.
Примеры
Входные данные
3 4 3 2 1 2 5
Выходные данные
12
Входные данные
3 4 3 2 1 3 5
Выходные данные
15
К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.
Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика).
Входные данные
Вводится число \(N\) — количество вагонов в поезде (1≤N≤2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до \(N\), каждое из которых встречается ровно один раз.
Выходные данные
Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите действия, которые нужно проделать с поездом. Каждое действие описывается двумя числами: типом и количеством вагонов:
1) если нужно завезти с пути 1 в тупик K вагонов, должно быть выведено сначала число 1, а затем — число \(K\) (\(K\)≥1),
2) если нужно вывезти из тупика на путь 2 K вагонов, должно быть выведено сначала число 2, а затем — число \(K\) (\(K\)≥1).
Если возможно несколько последовательностей действий, приводящих к нужному результату, выведите любую из них.
Если выстроить вагоны по порядку невозможно, выведите одно число 0.
Примеры
Входные данные
3 3 2 1
Выходные данные
YES
Входные данные
4 4 1 3 2
Выходные данные
YES
Входные данные
3 2 3 1
Выходные данные
NO
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D * обозначает привычное нам (B + C) * D, а запись A B C + D * + означает A + (B + C) * D.
Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения.
Дано выражение в постфиксой записи, содержащее однозначные числа, операции +, –, *. Вычислите значение записанного выражения.
Входные данные
В единственной строке записано выражение в постфиксной записи, содержащее однозначные числа и операции +, –, *. Строка содержит не более 100 чисел и операций. Числа и операции отделяются друг от друга ровно одним пробелом.
Выходные данные
Необходимо вывести значение записанного выражения. Гарантируется, что результат выражения, а также результаты всех промежуточных вычислений по модулю меньше \(2^{31}\).
Примеры
Входные данные
8 9 + 1 7 - *
Выходные данные
-102
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
64 megabytes
На барже располагается K грузовых отсеков. В каждый отсек можно поместить некоторое количество бочек с одним из 10 000 видов топлива. Причём извлечь бочку из отсека можно лишь в случае, если все бочки, помещённые в этот отсек после неё, уже были извлечены. Таким образом в каждый момент времени в каждом непустом отсеке имеется ровно одна бочка, которую можно извлечь не трогая остальных. Будем называть такие бочки крайними.
Изначально баржа пуста. Затем она последовательно проплывает через N доков, причём в каждом доке на баржу либо погружается бочка с некоторым видом топлива в некоторый отсек, либо выгружается крайняя бочка из некоторого отсека. Однако, если указанный отсек пуст, либо если выгруженная бочка содержит не тот вид топлива, который ожидалось, следует зафиксировать ошибку. Если на баржу оказывается погружено более P бочек или если после прохождения всех доков она не стала пуста, следует также зафиксировать ошибку. От вас требуется либо указать максимальное количество бочек, которые одновременно пребывали на барже либо зафиксировать ошибку.
Входные данные
В первой строке три целых числа N, K и P (1 ≤ N, K, P ≤ 100 000). Далее следует 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
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дана строка, составленная из круглых скобок. Определите, какое наименьшее количество символов необходимо удалить из этой строки, чтобы оставшиеся символы образовывали правильную скобочную последовательность.
Входные данные
Во входном файле записана строка из круглых скобок. Длина строки не превосходит \({100\,000}\) символов.
Выходные данные
Выведите единственное целое число — ответ на поставленную задачу.
Примеры
Входные данные
())(()
Выходные данные
2
Входные данные
))(((
Выходные данные
5
Выбрано
:
|