====== Вариант 4.3. Рейтинг результатов ====== [[:courses:algorithms_structures:cw_2026:grade4:start|Все варианты на «Хорошо»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]] Уровень: **Хорошо**. ===== Постановка задачи ===== score — результат игрока. Одинаковые баллы разных попыток сохраняются отдельно. Имена игроков в этом варианте не нужны. Разработайте систему хранения числовых результатов с повторениями. Требуются точный подсчёт, ранг, результат на заданной позиции и поиск ближайшего значения. Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат. ===== Данные и начальное состояние ===== * ''score'' — целое число от -1000000000 до 1000000000. * ''i'' — индекс в мысленно упорядоченной по возрастанию последовательности, начиная с 0. * Начальное состояние пустое; n учитывает все повторения, D — число различных результатов. ===== Операции ===== ^ Команда ^ Действие ^ Ответ ^ | ''ADD score'' | Добавить одно вхождение результата. | OK | | ''DEL score'' | Удалить одно вхождение результата. | OK; при отсутствии Error: NOT_FOUND | | ''COUNT score'' | Посчитать вхождения точного значения. | VALUE c | | ''RANK score'' | Посчитать все результаты строго меньше score, включая повторы. | VALUE r | | ''KTH i'' | Получить результат на позиции i по возрастанию, учитывая повторы. | VALUE score; если i вне [0,n), Error: RANGE | | ''NEAR score'' | Получить ближайшее сохранённое значение по абсолютной разности. | VALUE score; на пустом наборе NONE | ===== Правила выполнения и ошибки ===== При равных расстояниях NEAR возвращает меньшее значение. Удаление одного из повторений не удаляет остальные. COUNT отсутствующего значения и RANK на пустом наборе возвращают 0. При вычислении разности необходимо учитывать возможный выход за 32-битный знаковый диапазон. Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы. ===== Требования к эффективности ===== Все операции — O(log(n+2)) в худшем случае. Память — O(D+1); хранить каждое повторение отдельно не требуется и при больших кратностях не соответствует этой границе. Запросы RANK/KTH не должны просматривать все значения. В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях. ===== Формат ввода и вывода ===== Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта: Course work for option 4.3, created by Ivan Ivanov. Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием. ===== Примеры ===== ==== Пример 1. Повторения, ранг и позиция ==== Ввод: 1 6 ADD 10 ADD 20 ADD 20 RANK 20 KTH 2 COUNT 20 Вывод: Course work for option 4.3, created by Ivan Ivanov. OK OK OK VALUE 1 VALUE 20 VALUE 2 ==== Пример 2. Равные расстояния и удаление ==== Ввод: 1 5 ADD 10 ADD 20 NEAR 15 DEL 10 NEAR 15 Вывод: Course work for option 4.3, created by Ivan Ivanov. OK OK VALUE 10 OK VALUE 20 ==== Пример 3. Пустое состояние и ошибки ==== Ввод: 1 5 NEAR 0 KTH 0 ADD 5 DEL 7 COUNT 5 Вывод: Course work for option 4.3, created by Ivan Ivanov. NONE Error: RANGE OK Error: NOT_FOUND VALUE 1