Все варианты на «Удовлетворительно» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Удовлетворительно.
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 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
Ввод:
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
Ввод:
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