Информатика
>>
Олимпиады и турниры
>>
Всероссийская олимпиада по информатике
>>
2005 год
>>
задача 2
Фильтр
Выбрано 2 задачи Убрать все задачи
В ряд стоят 9 вертикальных столбиков. В некоторых местах между соседними столбиками вставлены горизонтальные палочки, никакие две из которых не находятся на одной высоте. Жук ползёт снизу вверх; когда он встречает палочку, он переползает по ней на соседний столбик и продолжает ползти вверх. Известно, что если жук начинает внизу первого столбика, то он закончит свой путь на девятом столбике. Всегда ли можно убрать одну из палочек так, чтобы жук в конце пути оказался наверху пятого столбика?
Решение|
Имя входного файла: |
memory.in |
|
Имя выходного файла: |
memory.out |
|
Максимальное время работы на одном тесте: |
2 секунды |
|
Максимальный объем используемой памяти: |
64 мегабайта |
|
Максимальная оценка за задачу: |
100 баллов |
Пете поручили написать менеджер памяти для новой стандартной библиотеки языка 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. Результаты нужно выводить в порядке следования запросов во входном файле.
Пример
|
memory.in |
memory.out |
|
6 8 2 3 -1 3 3 -5 2 2 |
1 3 -1 -1 1 -1 |
Решение
Задачи
Задача 98676[Менеджер памяти] |
|
|
|
Имя входного файла: |
memory.in |
|
Имя выходного файла: |
memory.out |
|
Максимальное время работы на одном тесте: |
2 секунды |
|
Максимальный объем используемой памяти: |
64 мегабайта |
|
Максимальная оценка за задачу: |
100 баллов |
Пете поручили написать менеджер памяти для новой стандартной библиотеки языка 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. Результаты нужно выводить в порядке следования запросов во входном файле.
Пример
|
memory.in |
memory.out |
|
6 8 2 3 -1 3 3 -5 2 2 |
1 3 -1 -1 1 -1 |
|
|
|
Решение |
Страница: 1 [Всего задач: 1]
