Все варианты на «Удовлетворительно» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Удовлетворительно.
Событие — просмотр товара. text — идентификатор просмотренного товара. Каждый просмотр, включая повторный, создаёт отдельное событие.
Разработайте программу хранения ограниченной истории событий. При поступлении нового события заполненная история теряет самое старое событие. Пользователь может изменить число сохраняемых событий.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
text — непустой токен события по общему формату.c — ёмкость от 0 до 100000; i — индекс записи, начиная с 0 от самой старой.| Команда | Действие | Ответ |
|---|---|---|
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 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
Ввод:
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
Ввод:
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