Содержание

Вариант 3.9. Отбор результатов для награждения

Все варианты на «Удовлетворительно» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты

Уровень: Удовлетворительно.

Постановка задачи

weight — положительный результат участника. Нужно последовательно отбирать лучшие результаты. Имена участников не хранятся, одинаковые результаты считаются отдельными экземплярами.

Разработайте программу хранения числовых характеристик объектов. Она должна быстро выдавать объект с наибольшим значением и показывать несколько наибольших значений без изменения сохранённых данных.

Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.

Данные и начальное состояние

Операции

Команда Действие Ответ
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.9, 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.9, 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.9, 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.9, created by Ivan Ivanov.
Error: EMPTY
OK
Error: RANGE
VALUE 7
VALUE 1