Содержание

Вариант 3.7. Недавно просмотренные товары

Все варианты на «Удовлетворительно» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты

Уровень: Удовлетворительно.

Постановка задачи

Событие — просмотр товара. text — идентификатор просмотренного товара. Каждый просмотр, включая повторный, создаёт отдельное событие.

Разработайте программу хранения ограниченной истории событий. При поступлении нового события заполненная история теряет самое старое событие. Пользователь может изменить число сохраняемых событий.

Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.

Данные и начальное состояние

Операции

Команда Действие Ответ
INIT c Очистить историю и установить ёмкость c. Повторная инициализация разрешена. OK
ADD text Добавить событие в конец; если места нет, удалить самое старое. При c=0 событие не сохраняется. OK
RESIZE c Изменить ёмкость. При уменьшении оставить c самых новых событий в прежнем относительном порядке. OK
GET i Получить запись с индексом i. VALUE text; если i вне [0,n), Error: RANGE
LIST Получить все сохранённые события от самого старого к самому новому. ITEMS n, затем n строк text

Правила выполнения и ошибки

Повторяющиеся события сохраняются отдельно. Расширение ёмкости не восстанавливает удалённые события. Все команды, кроме INIT, до инициализации возвращают Error: STATE после проверки синтаксиса и статических диапазонов аргументов.

Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.

Требования к эффективности

ADD и GET — O(1); RESIZE и INIT — O(c+n); LIST — O(n). Дополнительная память, включая хранение событий, — O©; длина каждого токена ограничена константой общего формата.

В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.

Формат ввода и вывода

Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:

Course work for option 3.7, created by Ivan Ivanov.

Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.

Примеры

Пример 1. Хранение и вытеснение

Ввод:

1
6
INIT 2
ADD first
ADD second
ADD third
LIST
GET 0

Вывод:

Course work for option 3.7, created by Ivan Ivanov.
OK
OK
OK
OK
ITEMS 2
second
third
VALUE second

Пример 2. Сжатие и последующее расширение

Ввод:

1
6
INIT 2
ADD first
ADD second
RESIZE 1
RESIZE 3
LIST

Вывод:

Course work for option 3.7, created by Ivan Ivanov.
OK
OK
OK
OK
OK
ITEMS 1
second

Пример 3. Ошибки и нулевая ёмкость

Ввод:

1
5
ADD first
INIT 0
ADD first
GET 0
LIST

Вывод:

Course work for option 3.7, created by Ivan Ivanov.
Error: STATE
OK
OK
Error: RANGE
ITEMS 0