Все варианты на «Удовлетворительно» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Удовлетворительно.
Ключ — квадратная матрица весов небольшого направленного графа, value — заранее вычисленная целая метрика. Вычисление метрики не требуется; перестановка вершин меняет матрицу и в общем случае ключ.
Разработайте кеш результатов вычислений для квадратных числовых таблиц. Результат передаётся программе готовым. Нужно сохранять его и находить по точному содержимому таблицы; вычислять сам результат не требуется.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
d — размер от 1 до 8; затем на той же строке передаются ровно d² целых элементов в порядке строк, слева направо и сверху вниз.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.12, created by Ivan Ivanov.
Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.
Ввод:
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.12, created by Ivan Ivanov. OK VALUE 10 OK VALUE 1 VALUE 11
Ввод:
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.12, created by Ivan Ivanov. OK NONE OK VALUE 0
Ввод:
1 5 PUT 1 5 25 PUT 1 1001 30 GET 1 5 GET 1 DEL 1 6
Вывод:
Course work for option 3.12, created by Ivan Ivanov. OK Error: RANGE VALUE 25 Error: INPUT Error: NOT_FOUND