Содержание
Общие требования к курсовым работам АиСД: интерфейс
Выполнение и обоснование
- Реализуйте все операции своего варианта.
- Структуры хранения данных и алгоритмы их обработки выберите самостоятельно.
- В отчёте перечислите операции, характеристики и объём данных, частоты операций и критерии оптимальности.
- Сравните выбранное решение как минимум с двумя применимыми альтернативами, обоснуйте выбор, оцените время всех операций и расход памяти. Различайте гарантированные, ожидаемые и амортизированные оценки.
- Требования на данной странице, а также требования описанные в варианте и регламенте обязательны; примеры показывают отдельные случаи, а не заменяют полное условие.
- Необходимые структуры и алгоритмы реализуются самостоятельно.
- Готовые контейнеры, выполняющие предметные операции задания, и готовые реализации алгоритмов обработки использовать нельзя.
- Разрешены базовые типы, строки, собственные классы и ввод/вывод.
- Python list и C++ std::vector разрешены только как индексируемое хранилище: выделение длины/ёмкости, чтение и запись по индексу, получение длины.
- Расширение с переносом содержимого, поиск, сортировку и другие предметные операции реализуйте самостоятельно.
- Готовые append/pop/insert/remove/sort, срезы и поиск через in для этой цели запрещены.
- Разбор входных строк стандартными средствами разрешён.
- В независимых тестах и обработке результатов экспериментов готовые контейнеры допустимы.
- Эксперименты и визуализация должны использовать ту же реализацию, что основное приложение.
- Исследуйте все операции на возрастающих объёмах и характерных случаях входа, зафиксируйте seed, среду, число повторов, медиану и разброс.
- Визуализация данных и промежуточных состояний выполняется отдельно от проверяемого stdout.
Языки, состав и запуск
- Python 3.12 (версия среды проверки): входной файл
src/main.py, запуск из src командойpython3 main.py. Собственные соседние модули разрешены. Сторонние пакеты не требуются и не используются. - C++17: в
src/Makefileкомандаmakeсобирает исполняемый файлcw; запуск из src командой./cw. Количество собственных исходных файлов не ограничено. Сторонние библиотеки не используются. - Программа читает stdin и пишет stdout, обязательных аргументов командной строки нет. Каждый запуск независим от предыдущих.
- Среда проверки: Python 3.12.3, C++17, Linux. Время нагрузки ограничено отдельно для группы вариантов и языка по таблице ниже; на процесс программы отводится 512 МБ адресного пространства, общий stdout/stderr ограничен 1 МБ
- Флаги C++17 и оптимизации задайте в Makefile; эталонная конфигурация — -std=c++17 -O2 без санитайзера.
- Границы данных и оценки сложности обязательны независимо от этих лимитов.
Обязательная первая строка
При любом запуске первой строкой stdout, до других сообщений, выводится:
Course work for option G.N, created by Name Surname.
Замените G.N на назначенный уровень и номер (например, 4.12), Name и Surname — на собственные имя и фамилию латиницей. Каждая часть имени должна соответствовать [A-Za-z][A-Za-z0-9_]*. Номер записывается без ведущих нулей: G — 3, 4 или 5, N — от 1 до 15. Пробелы и пунктуация должны совпадать с шаблоном; точка и перевод строки обязательны. Заголовок одинаков во всех запусках, включая справку и ошибочный ввод, и выводится один раз за запуск. Ivan Ivanov в примерах — условный автор.
Режим работы и строки команд
Первая строка stdin содержит одно целое число — режим:
6— сразу вывести непустую справку о командах своего варианта и завершиться. Читать q или ждать текст после 6 нельзя. Формулировки справки студент выбирает сам; они должны описывать синтаксис и назначение всех команд.1— в следующей строке прочитать одно число q от 0 до 100000, затем ровно q строк предметных команд. Ответить на каждую команду, сохраняя общее состояние между ними, после чего завершиться.
Иной корректно записанный целый режим, включая зарезервированные 8 и 9, даёт Error: COMMAND и завершение. Пустой stdin, неверный формат строки режима или q, отсутствующая строка q либо q вне диапазона дают Error: INPUT и завершение. При q=0 выводится только заголовок. Две пустые строки не являются признаком конца сценария. Данные после q команд не входят в допустимый вход и не тестируются.
Каждая команда целиком занимает одну строку. Разделители — один или несколько ASCII-пробелов или табуляций; такие разделители в начале и конце строки допустимы. Регистр команд учитывается. Вход может иметь переводы строк LF или CRLF. Последняя непустая строка может завершаться EOF без перевода строки.
Формат значений
- Общий строковый токен: от 1 до 64 символов из
A-Z,a-z,0-9,_и-. Пробелы внутри токена и кавычки не поддерживаются. Слова text/value не означают строку произвольной длины: это тоже один токен. Специальные форматы путей и имён задаются в вариантах. - Целое число имеет вид
-?[0-9]+: знак плюс, экспонента и десятичная точка запрещены. Ведущие нули и -0 разрешены. Число корректного формата вне допустимого диапазона даёт RANGE, а не INPUT. В режиме/q действует отдельное правило INPUT, описанное выше. - Если в варианте не указано иначе, диапазон числового значения от -1000000000 до 1000000000. Числовой id — от 1 до 1000000000. Числа в ответах печатаются без ведущих нулей и без плюса; ноль печатается как 0.
- Строки сравниваются лексикографически по ASCII с учётом регистра. Числа сравниваются численно. Для составных записей поля сравниваются слева направо, если вариант задаёт такой порядок.
- Одновременно хранится не более 100000 предметных записей, если в варианте не задан иной предел. Вход гарантированно не требует превысить предел количества записей, отношений и суммарного объёма данных; отдельный код ошибки переполнения таких пределов не требуется.
- Правильный полный вывод одного сценария автоматической проверки, включая заголовок, не превышает 1 МиБ в UTF-8. Это ограничение проверочных входов, а не разрешение обрезать правильный ответ.
- Вычисления сумм, расстояний и сроков должны корректно работать в знаковом 64-битном диапазоне. Входные сценарии гарантируют, что все промежуточные значения и запрашиваемые результаты в него помещаются; это отдельная гарантия допустимости сценария.
- Для сложности используйте n — текущее число записей, L — максимальную длину обрабатываемого строкового поля; дополнительные обозначения задаются в варианте.
- Обозначения в синтаксисе команд — места для значений, а не буквальный текст ввода, например:
- GET i означает GET 0 для i=0.
- Многоточие означает последовательность аргументов, которая раскрывается согласно условию.
- В ITEMS k буква k — фактическое число следующих строк;
- аналогично трактуются m/r в ответах.
- Оценки памяти и времени для пустого состояния допускают постоянные накладные расходы O(1).
- Выделенное хранилище после удалений может сохранять ёмкость до наибольшего достигнутого размера.
- Если требуется память O(n), это O(N+1), где N — наибольший достигнутый размер в сценарии
- зависимость от числа всех когда-либо выполненных команд вместо N не допускается, если явно не требуется хранение истории.
Ответы
Каждый ответ заканчивается переводом строки LF. Используйте ровно один пробел между полями, без пробелов в конце, без пустых строк и приглашений. stderr при штатной работе пуст.
| Вид ответа | Значение |
|---|---|
OK | Операция успешно выполнена. |
VALUE … | Одно значение или одна запись с полями в порядке из условия. |
NONE | Обычный результат отсутствия, если он предусмотрен данной командой. |
ITEMS k | После этой строки идут ровно k строк записей указанного формата. Для пустой выборки выводится только ITEMS 0. |
Error: CODE | Обработанная ошибка с одним из кодов ниже; это полный текст ответа, дополнительных пояснений нет. |
Ошибки и их порядок
| Код | Значение |
|---|---|
COMMAND | Неизвестная команда или неподдерживаемый режим. |
INPUT | Неверное число аргументов или лексический формат, пустая строка предметной команды, преждевременный конец ввода. |
RANGE | Неверный числовой диапазон или границы/индексы. |
NOT_FOUND | Отсутствует обязательный объект. |
EXISTS | Нарушается уникальность существующего объекта. |
EMPTY | Нет данных для извлечения либо отмены. |
STATE | Недопустимое состояние или нарушение предпосылки операции. |
Проверяйте ошибки в порядке:
- Имя команды: неизвестное непустое имя даёт COMMAND независимо от остальных аргументов.
- Число аргументов и их лексический формат: INPUT. Для строк с числом элементов n/d сначала проверяется формат и диапазон этого размера, затем число остальных аргументов.
- Статические диапазоны чисел: RANGE.
- Наличие требуемой инициализации: STATE.
- Индексы и границы, зависящие от текущего размера: RANGE.
- Существование обязательных объектов слева направо: NOT_FOUND; затем уникальность: EXISTS; затем прочие ограничения: STATE. Особенности прохода по путям явно заданы в соответствующих вариантах.
Если режим и q уже прочитаны, ошибка одной команды не меняет ни предметное состояние, ни время, ни порядок использования, ни историю отмены.
- После ошибочной команды исполняется следующая строка команды.
- Пустая строка считается одной ошибочной командой.
- Если EOF наступил до очередной строки из q, выведите один Error: INPUT и завершите работу (не печатайте ошибки за все оставшиеся строки).
- После обработанной ошибки программа завершается с кодом 0. Необработанное исключение и ненулевой код завершения не являются корректной обработкой ошибки.
Справка: пример
Ввод:
6
Один из допустимых ответов для варианта 3.1:
Course work for option 3.1, created by Ivan Ivanov. INIT c - clear history and set capacity ADD text - append an event RESIZE c - change capacity GET i - read an event LIST - print stored events
Справка не должна ожидать дополнительного ввода. Примеры предметных команд с полными входом и выходом приведены на странице каждого варианта.
Лимиты нагрузочных блоков
- Общий блок содержит два смешанных сценария с параметром размера 2048 и 18000.
- Размер не равен числу команд q: один сценарий выполняет несколько операций над данными.
- Блок оценивается целиком по суммарному времени (без учёта компиляции).
- Целевой блок содержит три независимых запуска на указанных размерах.
- Для каждого размера действуют свой предел времени и одинаковая доля баллов
- Размер не равен числу команд.
Критерии предварительного прохождения и доли баллов приведены в разделе 9 регламента. Для допуска необходимо полное прохождение, а не произвольный положительный балл.
| Варианты | Язык | Общий блок, с | Целевая операция | Размеры | Пределы размеров, с |
|---|---|---|---|---|---|
| 3.1, 3.6, 3.7 | Python | 1 | ADD | 8192, 16384, 32768 | 0.45, 0.65, 1 |
| 3.1, 3.6, 3.7 | C++ | 0.5 | ADD | 8192, 16384, 32768 | 0.25, 0.3, 0.5 |
| 3.2, 3.8, 3.9 | Python | 1.35 | PEEK | 8192, 16384, 32768 | 0.6, 0.9, 1.5 |
| 3.2, 3.8, 3.9 | C++ | 0.5 | PEEK | 8192, 16384, 32768 | 0.3, 0.4, 0.65 |
| 3.3, 3.10, 3.11 | Python | 1.8 | GET | 8192, 16384, 32768 | 0.65, 1.1, 1.95 |
| 3.3, 3.10, 3.11 | C++ | 0.75 | GET | 8192, 16384, 32768 | 0.3, 0.5, 0.85 |
| 3.4, 3.12, 3.13 | Python | 1.8 | GET | 8192, 16384, 32768 | 0.9, 1.6, 2.95 |
| 3.4, 3.12, 3.13 | C++ | 0.85 | GET | 8192, 16384, 32768 | 0.45, 0.7, 1.35 |
| 3.5, 3.14, 3.15 | Python | 3.45 | DOMAIN | 8192, 16384, 32768 | 0.8, 1.4, 2.55 |
| 3.5, 3.14, 3.15 | C++ | 1.15 | DOMAIN | 8192, 16384, 32768 | 0.35, 0.5, 0.9 |
| 4.1, 4.6, 4.7 | Python | 1.8 | LOWER | 8192, 16384, 32768 | 0.6, 0.95, 1.65 |
| 4.1, 4.6, 4.7 | C++ | 0.75 | LOWER | 8192, 16384, 32768 | 0.25, 0.45, 0.7 |
| 4.2, 4.8, 4.9 | Python | 2.8 | COUNT | 8192, 16384, 32768 | 0.55, 0.8, 1.55 |
| 4.2, 4.8, 4.9 | C++ | 0.85 | COUNT | 8192, 16384, 32768 | 0.25, 0.35, 0.6 |
| 4.3, 4.10, 4.11 | Python | 1.8 | RANK | 8192, 16384, 32768 | 0.65, 1.05, 2 |
| 4.3, 4.10, 4.11 | C++ | 0.7 | RANK | 8192, 16384, 32768 | 0.3, 0.35, 0.6 |
| 4.4, 4.12, 4.13 | Python | 1.3 | ADD + SUM | 8192, 16384, 32768 | 0.5, 0.7, 1.1 |
| 4.4, 4.12, 4.13 | C++ | 0.7 | ADD + SUM | 8192, 16384, 32768 | 0.25, 0.35, 0.6 |
| 4.5, 4.14, 4.15 | Python | 1.15 | DIST | 2048, 4096, 8192 | 0.45, 0.5, 0.6 |
| 4.5, 4.14, 4.15 | C++ | 0.5 | DIST | 2048, 4096, 8192 | 0.15, 0.2, 0.2 |
| 5.1, 5.6, 5.7 | Python | 1.85 | GET | 8192, 16384, 32768 | 0.75, 1.35, 2.55 |
| 5.1, 5.6, 5.7 | C++ | 0.9 | GET | 8192, 16384, 32768 | 0.35, 0.65, 1 |
| 5.2, 5.8, 5.9 | Python | 1.85 | COMMIT | 4096, 8192, 16384 | 0.65, 1.1, 1.95 |
| 5.2, 5.8, 5.9 | C++ | 1.1 | COMMIT | 4096, 8192, 16384 | 0.35, 0.6, 1.1 |
| 5.3, 5.10, 5.11 | Python | 3.05 | BACKLINKS | 4096, 8192, 16384 | 0.7, 1.2, 2.3 |
| 5.3, 5.10, 5.11 | C++ | 1 | BACKLINKS | 4096, 8192, 16384 | 0.3, 0.4, 0.7 |
| 5.4, 5.12, 5.13 | Python | 3.4 | NEXT | 8192, 16384, 32768 | 1.2, 2.2, 4.35 |
| 5.4, 5.12, 5.13 | C++ | 0.9 | NEXT | 8192, 16384, 32768 | 0.35, 0.55, 0.95 |
| 5.5, 5.14, 5.15 | Python | 2.4 | TICK | 8192, 16384, 32768 | 0.85, 1.45, 2.8 |
| 5.5, 5.14, 5.15 | C++ | 0.85 | TICK | 8192, 16384, 32768 | 0.35, 0.55, 1 |
Успешная нагрузка подтверждает ресурсные ограничения только на выполненных входах; требования к сложности и самостоятельной реализации остаются обязательными.
