====== Вариант 5.14. Кеш предварительно сформированных превью ====== [[:courses:algorithms_structures:cw_2026:grade5:start|Все варианты на «Отлично»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]] Уровень: **Отлично**. ===== Постановка задачи ===== key — идентификатор ресурса, value — токен уже сформированного превью. Создавать изображения не нужно; нужно хранить результаты до вытеснения или истечения. Разработайте ограниченный по ёмкости кеш с истечением срока хранения. При нехватке места удаляется запись, к которой дольше всего не обращались. Независимо от этого запись удаляется при наступлении её срока истечения. Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат. ===== Данные и начальное состояние ===== * ''key'', ''value'' — токены общего формата. * ''capacity'' — ёмкость от 1 до 100000; ''ttl'' — срок от 1 до 1000000000. * ''time'' — целый логический момент от 0 до 1000000000000. * До INIT кеш не инициализирован. INIT устанавливает время t=0; время меняет только TICK, а не выполнение других команд. ===== Операции ===== ^ Команда ^ Действие ^ Ответ ^ | ''INIT capacity'' | Очистить кеш, установить ёмкость и время 0; повторная инициализация разрешена. | OK | | ''PUT key value ttl'' | Добавить/обновить запись, назначив срок expires=t+ttl, и считать её самой недавно использованной. | OK | | ''GET key'' | Прочитать живую запись и считать её самой недавно использованной. | VALUE value; при отсутствии NONE | | ''PEEK key'' | Прочитать запись без изменения порядка использования. | VALUE value; при отсутствии NONE | | ''DEL key'' | Удалить запись. | OK; при отсутствии Error: NOT_FOUND | | ''TICK time'' | Установить время и удалить все записи с expires ≤ time. Уменьшать время нельзя. | OK; если time < t, Error: RANGE | | ''RESIZE capacity'' | Изменить ёмкость и вытеснить лишние записи от самых давно использованных. | OK | | ''LIST'' | Получить все живые записи от недавно к давно использованным. | ITEMS n, затем n строк key value expires | ===== Правила выполнения и ошибки ===== До INIT все команды, кроме INIT, после проверки синтаксиса и статических диапазонов возвращают STATE. Истечение при точном равенстве уже удаляет запись. Поскольку время меняется только TICK, перед остальными командами не требуется обращаться к часам ОС. PUT существующего ключа заменяет значение и срок, не увеличивая число записей. Успешные GET и PUT делают запись первой по недавности, неуспешный GET порядок не меняет. GET/PEEK не продлевают TTL. PEEK/LIST не меняют порядок. PUT нового ключа при заполнении вытесняет самую давно использованную запись. RESIZE сохраняет наиболее недавно использованные записи. Начальный/обновлённый срок может превышать 10^12 и вычисляется в int64. Для каждой живой записи сохраняется только один действующий срок; объём памяти не должен расти от повторных PUT одного ключа. Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы. ===== Требования к эффективности ===== GET/PEEK — ожидаемо O(L) либо гарантированно O(L·log(n+2)); PUT/DEL — не хуже O(L·log(n+2)). TICK — O(1+e·L·log(n+2)), где e — число истёкших записей; RESIZE — O(1+e·L·log(n+2)) для e вытеснений; LIST — O(nL). При отсутствии истёкших записей TICK не должен просматривать весь кеш. Память — O(capacity·L), включая все вспомогательные сведения, независимо от общего числа выполненных команд. В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях. ===== Формат ввода и вывода ===== Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта: Course work for option 5.14, created by Ivan Ivanov. Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием. ===== Примеры ===== ==== Пример 1. Вытеснение и срок хранения ==== Ввод: 1 9 INIT 2 PUT a x 5 PUT b y 9 GET a PUT c z 7 PEEK b TICK 5 PEEK a LIST Вывод: Course work for option 5.14, created by Ivan Ivanov. OK OK OK VALUE x OK NONE OK NONE ITEMS 1 c z 7 ==== Пример 2. Продление через PUT и точная граница ==== Ввод: 1 8 INIT 1 PUT a x 5 TICK 3 PUT a y 10 TICK 5 GET a TICK 13 GET a Вывод: Course work for option 5.14, created by Ivan Ivanov. OK OK OK OK OK VALUE y OK NONE ==== Пример 3. Неудачная смена времени ==== Ввод: 1 7 INIT 2 PUT a x 10 TICK 4 TICK 3 PEEK a DEL b LIST Вывод: Course work for option 5.14, created by Ivan Ivanov. OK OK OK Error: RANGE VALUE x Error: NOT_FOUND ITEMS 1 a x 10