====== Вариант 3.4. Кеш результатов вычислений ======
[[:courses:algorithms_structures:cw_2026:grade3:start|Все варианты на «Удовлетворительно»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]]
Уровень: **Удовлетворительно**.
===== Постановка задачи =====
Ключ — квадратная матрица. 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.4, 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.4, 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.4, 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.4, created by Ivan Ivanov.
OK
Error: RANGE
VALUE 25
Error: INPUT
Error: NOT_FOUND