Инструменты пользователя

Инструменты сайта


courses:algorithms_structures:cw_2026:grade3:9

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

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

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.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
courses/algorithms_structures/cw_2026/grade3/9.txt · Последнее изменение: — 127.0.0.1