Инструменты пользователя

Инструменты сайта


courses:algorithms_structures:cw_2026:requirements

Общие требования к курсовым работам АиСД: интерфейс

Выполнение и обоснование

  • Реализуйте все операции своего варианта.
  • Структуры хранения данных и алгоритмы их обработки выберите самостоятельно.
  • В отчёте перечислите операции, характеристики и объём данных, частоты операций и критерии оптимальности.
    • Сравните выбранное решение как минимум с двумя применимыми альтернативами, обоснуйте выбор, оцените время всех операций и расход памяти. Различайте гарантированные, ожидаемые и амортизированные оценки.
  • Требования на данной странице, а также требования описанные в варианте и регламенте обязательны; примеры показывают отдельные случаи, а не заменяют полное условие.
  • Необходимые структуры и алгоритмы реализуются самостоятельно.
  • Готовые контейнеры, выполняющие предметные операции задания, и готовые реализации алгоритмов обработки использовать нельзя.
  • Разрешены базовые типы, строки, собственные классы и ввод/вывод.
  • 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 Недопустимое состояние или нарушение предпосылки операции.

Проверяйте ошибки в порядке:

  1. Имя команды: неизвестное непустое имя даёт COMMAND независимо от остальных аргументов.
  2. Число аргументов и их лексический формат: INPUT. Для строк с числом элементов n/d сначала проверяется формат и диапазон этого размера, затем число остальных аргументов.
  3. Статические диапазоны чисел: RANGE.
  4. Наличие требуемой инициализации: STATE.
  5. Индексы и границы, зависящие от текущего размера: RANGE.
  6. Существование обязательных объектов слева направо: 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

Успешная нагрузка подтверждает ресурсные ограничения только на выполненных входах; требования к сложности и самостоятельной реализации остаются обязательными.

courses/algorithms_structures/cw_2026/requirements.txt · Последнее изменение: — dmitry.ivanov