Содержание

Вариант 4.3. Рейтинг результатов

Все варианты на «Хорошо» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты

Уровень: Хорошо.

Постановка задачи

score — результат игрока. Одинаковые баллы разных попыток сохраняются отдельно. Имена игроков в этом варианте не нужны.

Разработайте систему хранения числовых результатов с повторениями. Требуются точный подсчёт, ранг, результат на заданной позиции и поиск ближайшего значения.

Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.

Данные и начальное состояние

Операции

Команда Действие Ответ
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