====== Вариант 3.9. Отбор результатов для награждения ======
[[:courses:algorithms_structures:cw_2026:grade3:start|Все варианты на «Удовлетворительно»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]]
Уровень: **Удовлетворительно**.
===== Постановка задачи =====
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