====== Вариант 4.11. Рейтинг времени прохождения ======
[[: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.11, 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.11, 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.11, 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.11, created by Ivan Ivanov.
NONE
Error: RANGE
OK
Error: NOT_FOUND
VALUE 1