====== Вариант 3.2. Выдача товара максимального веса ====== [[: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.2, 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.2, 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.2, 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.2, created by Ivan Ivanov. Error: EMPTY OK Error: RANGE VALUE 7 VALUE 1