ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98676
Тема:    [ Куча ]
Сложность: 5
Классы: 8,9,10,11
Название задачи: Менеджер памяти.
В корзину
Прислать комментарий

Условие

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

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 ≤ iM) содержит либо положительное число K, если i-й запрос - запрос на выделение с параметром K (1 ≤ KN), либо отрицательное число -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


Также доступны документы в формате DOC

Решение


Генератор тестов и проверяющая программа
Решения, написанные членами научного комитета и жюри Всероссийской олимпиады

Разбор задачи "Менеджер памяти"

Разобьем всю память на отрезки, каждый из которых состоит либо из свободных, либо из занятых (выделенных в ответ на запросы) ячеек.

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

Нам необходимо уметь:

  1. по заданному объёму памяти находить свободный отрезок, из которого данный объём можно выделить;
  2. по номеру запроса находить занятый отрезок, выделенный этим отрезком;
  3. по занятому отрезку находить свободные отрезки, находящиеся непосредственно перед и после него.

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

Будем использовать следующие структуры данных:

  1. двусвязный список свободных отрезков;
  2. массив запросов, где индексом является номер запроса, а значением - выделенный при выполнении этого запроса отрезок (или некоторое специальное значение вроде "nil" или "NULL", если память выделена не была или запрос не был запросом на выделение);
  3. кучу (heap) из указателей на свободные отрезки; куча строится по их длинам.

(Куча и двусвязный список должны содержать одни и те же свободные отрезки; этого можно добиться, используя указатели или классы Delphi и Visual Basic.)

Куча - это массив из N чисел H1, ..., HN, таких, что для любого i, 1 < i ≤ N, выполняется условие H[i/2] ≥Hi. Первый элемент в куче всегда не меньше остальных ее элементов, поэтому операция нахождения максимума в куче выполняется за время O(1). Можно реализовать операции добавления элементов в кучу, удаления из нее и изменения элемента за время O(log N); как это сделать, описано, например, в книге Т. Кормена, Ч. Лейзерсона, Р. Ривеста "Алгоритмы: построение и анализ", М.. МЦНМО, 2000.

Обработка запроса на выделение памяти производится следующим образом. Рассмотрим самый длинный свободный отрезок A: с помощью кучи мы можем найти его в списке за O(1). Если длины отрезка A недостаточно, чтобы вместить требуемый блок памяти, то такой блок невозможно разместить. Иначе мы размещаем данный блок, вставляя соответствующий занятый отрезок в список и укорачивая отрезок A.

Обработка запроса на освобождение памяти производится следующим образом. Мы удаляем соответствующий занятый отрезок A из списка, после чего разбираем 4 случая:

  1. Непосредственно слева и справа от A не располагается свободного отрезка. В этом случае мы делаем A свободным отрезком и добавляем его в кучу.
  2. Непосредственно слева от A не располагается свободного отрезка, непосредственно справа от A располагается свободный отрезок B. В этом случае мы удаляем отрезок A из списка и удлиняем отрезок B.
  3. Непосредственно справа от A не располагается свободного отрезка, непосредственно слева от A располагается свободный отрезок. Действуем аналогично случаю 2.
  4. Непосредственно слева от A располагается свободный отрезок B, непосредственно справа от A располагается свободный отрезок C. В этом случае мы удаляем отрезки A и C из списка и удлиняем отрезок B.

Также доступны документы в формате DOC

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по информатике
предмет информатика
год
Дата 2005 год
Номер 17
Место проведения Новосибирск
задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .