====== Вариант 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