Инструменты пользователя

Инструменты сайта


courses:algorithms_structures:cw_2026:grade3:13

Вариант 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
courses/algorithms_structures/cw_2026/grade3/13.txt · Последнее изменение: — 127.0.0.1