Содержание
Вариант 3.13. Кеш оценок числовых блоков
Все варианты на «Удовлетворительно» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Удовлетворительно.
Постановка задачи
Ключ — квадратный блок числовых данных, value — заранее вычисленная оценка этого блока. Требуется кеширование, а не алгоритм вычисления оценки.
Разработайте кеш результатов вычислений для квадратных числовых таблиц. Результат передаётся программе готовым. Нужно сохранять его и находить по точному содержимому таблицы; вычислять сам результат не требуется.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
Данные и начальное состояние
d— размер от 1 до 8; затем на той же строке передаются ровно d² целых элементов в порядке строк, слева направо и сверху вниз.- Элементы лежат в диапазоне от -1000 до 1000.
value— целое число от -1000000000 до 1000000000. - Начальное состояние пустое.
Операции
| Команда | Действие | Ответ |
|---|---|---|
PUT d a1 … a(d*d) value | Сохранить результат для таблицы, заменив прежний, если он был. | OK |
GET d a1 … a(d*d) | Получить результат для точно такой же таблицы. | VALUE value; при отсутствии NONE |
DEL d a1 … a(d*d) | Удалить сохранённый результат. | OK; при отсутствии Error: NOT_FOUND |
COUNT | Получить число различных сохранённых таблиц. | VALUE n |
Правила выполнения и ошибки
Таблицы равны только при одинаковом d и равенстве всех соответствующих элементов. Перестановка элементов, строк или столбцов в общем случае меняет ключ. Повторный PUT того же ключа не увеличивает COUNT. После проверки формата d проверяется его диапазон, затем количество остальных аргументов.
Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.
Требования к эффективности
PUT, GET и DEL — ожидаемо амортизированно O(d²) с допустимым худшим случаем O(n·d²), либо гарантированно O(d²·log(n+2)). COUNT — O(1). Память — O(суммы d² по сохранённым ключам). Сравнивать все сохранённые таблицы при каждом обычном поиске нельзя.
В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.
Формат ввода и вывода
Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:
Course work for option 3.13, created by Ivan Ivanov.
Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.
Примеры
Пример 1. Сохранение и замена
Ввод:
1 5 PUT 2 1 2 3 4 10 GET 2 1 2 3 4 PUT 2 1 2 3 4 11 COUNT GET 2 1 2 3 4
Вывод:
Course work for option 3.13, created by Ivan Ivanov. OK VALUE 10 OK VALUE 1 VALUE 11
Пример 2. Порядок элементов имеет значение
Ввод:
1 4 PUT 2 1 2 3 4 10 GET 2 1 3 2 4 DEL 2 1 2 3 4 COUNT
Вывод:
Course work for option 3.13, created by Ivan Ivanov. OK NONE OK VALUE 0
Пример 3. Неверные данные
Ввод:
1 5 PUT 1 5 25 PUT 1 1001 30 GET 1 5 GET 1 DEL 1 6
Вывод:
Course work for option 3.13, created by Ivan Ivanov. OK Error: RANGE VALUE 25 Error: INPUT Error: NOT_FOUND
