Пете поручили написать менеджер памяти для новой стандартной библиотеки языка H++. В распоряжении у менеджера находится массив из N последовательных ячеек памяти, пронумерованных от 1 до N. Задача менеджера — обрабатывать запросы приложений на выделение и освобождение памяти.
Запрос на выделение памяти имеет один параметр K. Такой запрос означает, что приложение просит выделить ему K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом непосредственно перед самой первой ячейкой памяти выделяемого блока не должно располагаться свободной ячейки памяти. После этого выделенные ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется.
Запрос на освобождение памяти имеет один параметр T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T — запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется.
Требуется написать менеджер памяти, удовлетворяющий приведенным критериям.
В первой строке входных данных задаются числа N и M — количество ячеек памяти и количество запросов, соответственно (1 ≤ N ≤ 231 – 1; 1 ≤ M ≤ 105). Каждая из следующих M строк содержит по одному числу: (i+1)-я строка входных данных (1 ≤ i ≤ M) содержит либо положительное число K, если i-й запрос — запрос на выделение с параметром K (1 ≤ K ≤ N), либо отрицательное число –T, если i-й запрос — запрос на освобождение с параметром T (1 ≤ T < i).
Для каждого запроса на выделение памяти выведите результат обработки этого запроса: для успешных запросов выведите номер первой ячейки памяти в выделенном блоке, для отклоненных запросов выведите число –1. Результаты нужно выводить в порядке следования запросов во входных данных
42 9 7 3 8 -2 6 5 -5 9 4
1 8 11 19 25 30 19
Клавиатура сотового телефона выглядит так:
|
1 — пробел |
2 — abc |
3 — def |
|
4 — ghi |
5 — jkl |
6 — mno |
|
7 — pqrs |
8 — tuv |
9 — wxyz |
Режим ввода T2005 устроен следующим образом. В телефоне есть словарь. Пользователь, чтобы ввести слово, последовательно нажимает клавиши, на которых написаны буквы этого слова. Например, чтобы ввести слово begin пользователь должен нажимать клавиши 23446. Но как только в словаре оказывается только одно слово с таким началом, это слово автоматически подставляется и, кроме того, после этого слова автоматически добавляется пробел. Например, пусть пользователь нажал клавиши 234, и оказалось, что слов, ввод которых начинается с нажатия именно этих клавиш, — ровно одно. Тогда автоматически подставится это слово и пробел после него, а все последующие нажатия клавиш уже будут относиться к вводу следующего слова.
Если для ввода какого-то слова нужно нажать последовательность клавиш, которая может являться началом какого-то другого слова, то после ввода этого слова нужно нажать клавишу 1, что соответствует вводу пробела. При вводе пробела считается, что вы ввели все слово целиком (а не только какое-либо его начало). Если после ввода пробела оказалось, что в словаре такой последовательности клавиш удовлетворяет несколько слов, подставляется первое из них в алфавитном порядке. Если (опять же после ввода пробела) оказалось, что в словаре нет слова, которое может быть введено такой последовательностью клавиш, то все, что было введено после предыдущего пробела (введенного или автоматически подставленного, или, если в тексте ранее не встречалось ни одного пробела — от начала текста) удаляется. Если после ввода пробела (как нажатием "1", так и автоподстановкой) или в начале текста нажимается клавиша "1", то ее нажатие игнорируется.
Вам дан словарь и последовательность нажатий клавиш. Выведите текст, который был введен пользователем.
Примечание: в тексте используются только маленькие латинские буквы и символ пробел.
Сначала на вход программы поступает число N — количество слов в словаре (2≤N≤100000). В следующих N строках задается словарь. Каждое слово записано в отдельной строке. Слова расположены в алфавитном порядке. Никакое слово в словаре не встречается дважды. Длина каждого слова не превосходит 10 символов.
Далее вводится число M — количество нажатий клавиш (1≤M≤20000). Затем задается M разделяющихся пробелами чисел, описывающих нажатые клавиши. Последней нажатой клавишей всегда является клавиша "1".
Выведите одну строку — текст, который оказался введен пользователем. Пробел после последнего введенного слова также должен быть выведен.
Примечание:
|
2 |
Примечание: в этом примере выходной файл должен быть создан, но должен быть пустым, в частности, в него не нужно выводить пробел. |
Оценка задачи
1 балл получат программы, правильно решающие задачу при ограничениях 2≤N≤100, 1≤M≤200.
5 po pod sasha shla shosse 12 7 4 5 7 2 7 6 1 7 4 6 1
shla sasha po shosse
2 sem vosem 6 7 8 9 7 8 1
sem vosem
На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).
Дано расписание движения электричек, в котором для каждой электрички указано время ее прибытия, а также время отправления в следующий рейс. Электрички в расписании упорядочены по времени прибытия. Поскольку вокзал — конечная станция, то электричка может стоять на нем довольно долго, в частности, электричка, которая прибывает раньше другой, отправляться обратно может значительно позднее.
Тупики пронумерованы числами от 1 до K. Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого-то тупика отправилась в момент времени X, то электричку, которая прибывает в момент времени X, в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 — можно.
Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.
Сначала вводятся число K — количество тупиков и число N — количество электропоездов (1≤K≤100000, 1≤N≤100000). Далее следуют N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 109. Никакие две электрички не прибывают в одно и то же время, но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая-нибудь электричка (или даже несколько) отправляются в момент прибытия какой-нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия.
Все электрички упорядочены по времени прибытия. Считается, что в нулевой момент времени все тупики на вокзале свободны.
Выведите Nчисел — по одному для каждой электрички: номер тупика, куда прибудет соответствующая электричка. Если тупиков не достаточно для того, чтобы организовать движение электричек согласно расписанию, выведите два числа: первое должно равняться 0 (нулю), а второе содержать номер первой из электричек, которая не сможет прибыть на вокзал.
1 1 2 5
1
1 2 2 5 5 6
0 2
2 3 1 3 2 6 4 5
1 2 1
Специальный терминал, разработанный в лаборатории, где работает Дима, представляет собой горизонтальный прямоугольник, состоящий из m×n ячеек, каждая из которых может содержать произвольное целое число. Ячейки занумерованы парами чисел, левая верхняя ячейка имеет номер (1, 1), правая нижняя – (\(m\), \(n\)).
Специальное устройство ввода, сконструированное специально для этого терминала, позволяет отправлять терминалу две команды: \(A\)(\(r\), \(c\), \(d\), \(v\)) и \(B\)(\(r_1\), \(c_1\), \(r_2\), \(c_2\), \(d\), \(v\)).
Рассмотрим сначала команду \(A\). Параметры \(r\) и \(c\) изменяются в пределах от 1 до \(m\) и от 1 до \(n\) соответственно и указывают, к какой ячейке применяется команда. Параметр \(d\) может принимать значение из множества {\(L\), \(R\), \(U\), \(D\)} и задает направление, в котором применяется команда: влево, вправо, вверх или вниз соответственно. Параметр \(v\) представляет собой целое неотрицательное число. В результате выполнения команды значения во всех ячейках, находящихся в направлении \(d\) от ячейки (\(r\), \(c\)), включая эту ячейку, увеличиваются на \(v\).
Например, если терминал имеет размер 5×4, то после выполнения команды \(A\)(3, 2, \(R\), 3) значения в ячейках (3, 2), (3, 3) и (3, 4) увеличатся на 3, а после команды \(A\)(2, 1, \(U\), 2) значения в ячейках (2, 1) и (1, 1) увеличатся на 2.
Рассмотрим теперь команду \(B\). Первые четыре ее параметра являются целыми числами и удовлетворяют условиям 1\( \le\) \(r_1\) \(\le\) \(r_2\) \(\le\) \(m\) и 1\( \le\) \(c_1\) \(\le\) \(c_2\) \(\le\) \(n\). Параметры \(d\) и \(v\) могут принимать те же значения, что и соответствующие параметры команды \(A\). Команда \(B\) выполняется следующим образом: для всех пар (\(r\), \(c\)), таких, что \(r_1\) \(\le\) \(r\) \(\le\) \(r_2\) и \(c_1\) \(\le\) \(c\) \(\le\) \(c_2\) выполняется команда \(A\)(\(r\), \(c\), \(d\), \(v\)).
Исходно все ячейки терминала содержат нули. Выведите содержимое терминала после выполнения заданной последовательности команд.
В первой строке вводятся числа \(m\) и \(n\), ( 1\( \le\)m, n\( \le\)200). В следующей строке задается число \(k\) – количество команд, которые следует обработать ( 0\( \le\)k\( \le\)40 000). Далее идут \(k\) строк, содержащих описания команд. Первый символ каждой строки задает тип команды, затем следует пробел и параметры команды, каждые два последовательных параметра разделены ровно одним пробелом. Параметр \(v\) каждой команды неотрицателен и не превышает 100.
Общее число команд \(A\), которое потребуется выполнить на терминале, включая команды, которые придется выполнить при выполнении команд \(B\), не превышает 5 * \(10^6\).
Выведите \(m\) строк по \(n\) чисел в каждой – содержимое терминала после выполнения указанной последовательности команд.
5 4 4 A 2 2 D 1 A 3 4 L 2 B 2 3 3 4 U 13 B 1 1 2 1 R 5
5 5 31 31 5 6 31 31 2 3 15 15 0 1 0 0 0 1 0 0
После победы в великой битве Король Ягуар хочет построить пирамиду, которая будет одновременно монументом в честь победы и гробницей для погибших солдат. Пирамида будет построена на поле боя. Она должна иметь прямоугольное основание, состоящее из \(a\) столбцов и \(b\) строк. Для сохранения останков и оружия павших солдат внутри основания пирамиды будет располагаться небольшая прямоугольная комната, состоящая из \(c\) столбцов и \(d\) строк.
Архитекторы Короля представили поле боя в виде прямоугольной сетки. Эта сетка состоит из квадратных клеток единичной площади и имеет \(m\) столбцов и \(n\) строк. Для каждой клетки они измерили ее высоту и получили некоторое целое число.
Основание пирамиды и комната должны покрывать включаемые ими клетки полностью, а их стороны должны быть параллельны сторонам поля боя. Высоты клеток, составляющих комнату, должны остаться неизменными, а высоты всех клеток основания пирамиды будут выровнены с помощью перемещения песка с более высоких клеток на более низкие. В результате этого высота основания пирамиды будет равна среднему арифметическому высот всех его клеток (за исключением клеток комнаты). Архитекторы могут выбрать любое местоположение для комнаты внутри пирамиды, но обязательно оставлять вокруг комнаты стену основания пирамиды толщиной хотя бы в одну клетку.
Помогите архитекторам выбрать наилучшее место для расположения пирамиды и комнаты внутри нее так, чтобы высота основания пирамиды была максимально возможной при заданных размерах.
На рисунке показан пример поля боя, где число в каждой клетке обозначает ее высоту. Клетки, составляющие основание пирамиды, обозначены серым цветом, а белые клетки внутри основания пирамиды соответствуют расположению комнаты. На этом рисунке представлен пример оптимального решения.
Напишите программу, которая по заданным размерам поля боя, пирамиды и комнаты, а также по заданным высотам всех клеток будет находить такое расположение пирамиды и комнаты внутри нее, что получившаяся высота основания пирамиды будет максимально возможной.
3 ≤ \(m\) ≤ 1000
3 ≤ \(n\) ≤ 1000
3 ≤ \(a\) ≤ \(m\)
3 ≤ \(b\) ≤ \(n\)
1 ≤ \(c\) ≤ \(a\) – 2
1 ≤ \(d\) ≤ \(b\) – 2
Все высоты – целые числа от 1 до 100.
Ваша программа получает входные данные в следующем формате:
СТРОКА 1: Содержит шесть целых чисел, разделенных пробелами, в следующем порядке: \(m\), \(n\), \(a\), \(b\), \(c\) и \(d\).
СЛЕДУЮЩИЕ \(n\) СТРОК: Каждая из этих строк содержит m целых чисел, разделенных пробелами. Эти числа соответствуют высотам клеток в одной строке сетки. Первая из этих строк соответствует верхней строке (строке 1) сетки, а последняя – нижней строке (строке \(n\)). При этом \(m\) чисел в каждой строке соответствуют высотам клеток этой строки, начиная со столбца 1.
Ваша программа должна вывести следующие данные:
СТРОКА 1: Должна содержать два целых числа, разделенные пробелом, – координаты левой верхней клетки основания пирамиды, при этом первое число соответствует столбцу, а второе – строке.
СТРОКА 2: Должна содержать два целых числа, разделенные пробелом, – координаты левой верхней клетки комнаты, при этом первое число соответствует столбцу, а второе – строке.
Если существует несколько оптимальных положений пирамиды и комнаты, выведите любое из них.
Ряд тестов с общей суммой 30 баллов будет удовлетворять следующим ограничениям:
3 ≤ \(m\) ≤ 10
3 ≤ \(n\) ≤ 10
8 5 5 3 2 1 1 5 10 3 7 1 2 5 6 12 4 4 3 3 1 5 2 4 3 1 6 6 19 8 1 1 1 3 4 2 4 5 6 6 3 3 3 2 2 2
1 4 1 6 2