Содержание
Вариант 3.8. Очередь обращений по срочности
Все варианты на «Удовлетворительно» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Удовлетворительно.
Постановка задачи
weight — срочность обращения. Нужно обслуживать обращения с наибольшей срочностью. Хранятся только значения срочности; идентификаторы заявителей и порядок равных обращений не требуются.
Разработайте программу хранения числовых характеристик объектов. Она должна быстро выдавать объект с наибольшим значением и показывать несколько наибольших значений без изменения сохранённых данных.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
Данные и начальное состояние
weight— целое число от 1 до 1000000000.k— целое число от 0 до 100000.- Начальное состояние пустое; отдельная инициализация не нужна. Хранятся только числовые значения, без идентификаторов объектов.
Операции
| Команда | Действие | Ответ |
|---|---|---|
PUSH weight | Добавить один экземпляр значения. | OK |
PEEK | Получить максимальное значение, не удаляя его. | VALUE weight; если данных нет, Error: EMPTY |
POP | Удалить один экземпляр максимального значения. | VALUE weight; если данных нет, Error: EMPTY |
COUNT | Получить число сохранённых экземпляров. | VALUE n |
TOP k | Получить min(k,n) наибольших значений по убыванию без удаления. | ITEMS m, затем m строк weight |
Правила выполнения и ошибки
Одинаковые значения сохраняются с кратностью. TOP и PEEK не меняют состояние. При k=0 ответ ITEMS 0. После POP удаляется только один экземпляр максимума.
Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.
Требования к эффективности
PUSH и POP — амортизированно O(log(n+2)); PEEK и COUNT — O(1). Для TOP допускается O(n + m·log(n+2)) и O(n) временной памяти. Основная память — O(n).
В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.
Формат ввода и вывода
Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:
Course work for option 3.8, created by Ivan Ivanov.
Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.
Примеры
Пример 1. Максимум и повторения
Ввод:
1 6 PUSH 8 PUSH 3 PUSH 8 TOP 2 POP COUNT
Вывод:
Course work for option 3.8, created by Ivan Ivanov. OK OK OK ITEMS 2 8 8 VALUE 8 VALUE 2
Пример 2. Выборка не удаляет данные
Ввод:
1 4 PUSH 4 TOP 0 TOP 5 COUNT
Вывод:
Course work for option 3.8, created by Ivan Ivanov. OK ITEMS 0 ITEMS 1 4 VALUE 1
Пример 3. Ошибки и сохранение данных
Ввод:
1 5 POP PUSH 7 PUSH 0 PEEK COUNT
Вывод:
Course work for option 3.8, created by Ivan Ivanov. Error: EMPTY OK Error: RANGE VALUE 7 VALUE 1
