====== Вариант 3.6. Буфер показаний датчика ======
[[:courses:algorithms_structures:cw_2026:grade3:start|Все варианты на «Удовлетворительно»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]]
Уровень: **Удовлетворительно**.
===== Постановка задачи =====
Событие — показание датчика. text — условное текстовое обозначение измерения, включая его тип или метку; арифметические действия над ним не нужны. Хранятся последние c измерений.
Разработайте программу хранения ограниченной истории событий. При поступлении нового события заполненная история теряет самое старое событие. Пользователь может изменить число сохраняемых событий.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
===== Данные и начальное состояние =====
* ''text'' — непустой токен события по общему формату.
* ''c'' — ёмкость от 0 до 100000; ''i'' — индекс записи, начиная с 0 от самой старой.
* До первой команды INIT история не инициализирована.
===== Операции =====
^ Команда ^ Действие ^ Ответ ^
| ''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(c); длина каждого токена ограничена константой общего формата.
В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.
===== Формат ввода и вывода =====
Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:
Course work for option 3.6, 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.6, 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.6, 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.6, created by Ivan Ivanov.
Error: STATE
OK
OK
Error: RANGE
ITEMS 0