Инженерный тур. 2 этап

На заключительном этапе в командном туре каждая команда профиля Технологии беспроводной связи работает с экспериментальными стендами, входящими в одноименный образовательный комплекс. Его программно-аппаратная платформа позволяет взаимодействовать с адаптивными алгоритмами и точностью передачи сигнала.

В современном мире все большее значение имеют технологии передачи больших зашифрованных массивов данных, в рамках которых при обмене сравнительно небольшими динамически изменяющимися ключами можно осуществлять доверенное шифрование и дешифрование. Задачи профиля связаны с актуальными задачами систем связи, включая:

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

Ключевые области применения связаны с космосом, промышленным интернетом вещей, подводной и мобильной робототехникой, каналами связи для роевых устройств.

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

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

Второй этап (дистанционный командный) — отборочный этап, задачи которого подобраны таким образом, чтобы объективно проверить индивидуальные знания участников и косвенно оценить личный вклад участников в результат командной работы. Это не только отборочное соревнование, но прежде всего — введение в профиль. То есть его содержание (задачи, динамика) несет образовательную составляющую, причем не только в рамках подготовки к заключительному этапу, но и для развития общих навыков (командное взаимодействие, работа со сложными моделями, информационный поиск и нестандартное мышление).

Второй этап профиля Технологии беспроводной связи включает в себя шесть командных задач. Все они сочетают в себе математику и информатику. Для решения требуются не только школьные знания, программные умения и навыки их применения в решении новых задач, но и факультативные знания в области программирования, математики и геометрии. Методические рекомендации к данному этапу позволяют очертить область знаний и навыков для самостоятельного изучения.

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

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

Во время второго отборочного этапа участники решают задачи, которые отражают часть большой командной задачи заключительного этапа, и знакомятся с базовыми концепциями — работают с кодами, потоками и форматами данных, протоколами. Ниже представлена схема связей тем задач второго тура и навыков, необходимых для решения задач заключительного этапа.

Рис. 1.1. ТБС Схема связей тем задач

Анализ данных

Информация — главный ресурс, с которым участники работают на этом профиле, и важно уметь анализировать и обрабатывать ее в зависимости от задачи. При работе с этим разделом важно обращать внимание на формат данных, так как их представление может быть крайне разнообразно.

Кодирование-декодирование

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

Алгоритмы

Задача заключительного этапа предполагает написание программного кода, и здесь важную роль играет навык разработки алгоритмов, равно как и поиска подходящих типовых. На проработку этих навыков и рассчитаны задачи раздела «Алгоритмы». При работе с ними важно делать акцент на информационном поиске и умении выявить типовую подзадачу.

Анализ кода

Правильный выбор кода, в зависимости от задачи, дает половину решения. Эти задания позволят рассмотреть коды в разных аспектах, увидеть типичные проблемы и, как следствие, более осознанно и осмысленно подойти к этой части задачи заключительного этапа.

Канал связи

Одна из составляющих процесса передачи данных — канал связи, обладающий своими характеристиками. Этот раздел содержит задачи, связанные с анализом этих характеристик, в основном отраженных в вероятностной форме. Поэтому при решении понадобятся, как минимум, базовые знания теории вероятностей.

Автономное управление

Часть задачи заключительного этапа составляет разработка алгоритма автономного управления спутником, качество которого напрямую влияет на общий результат, поэтому важно понимать принципы автономности и обладать навыками создания самостоятельных алгоритмов. Хотя в некоторой степени это характерно для всех заданий, задачи этого раздела направлены именно на автономику.

Все задачи второго отборочного этапа решаются на платформе Яндекс.Контест. В заданное время всем участникам открывается доступ к очередному набору задач (их условиям и проверочной системе). Участники должны написать программу на одном из языков программирования: Python 3.12, Java 17, C++20, C17, и загрузить ее текст на сервер. На сервере выполняется тестирование загруженной программы: ее ответы сверяются с ответами эталонного решения, составленного авторами. Их решение требует наличие базовых навыков программирования, поскольку это является необходимой частью задания. Ввод данных в программу осуществляется через стандартный ввод (stdin), вывод данных — через стандартный вывод (stdout). Случайные числа, используемые для генерации тестов, являются псевдослучайными. Все проверки программ всех участников производятся на одинаковых данных.

Командная работа начинается именно во время второго этапа. Помимо общих механизмов, для профиля создано условие на командное взаимодействие — ограниченное число попыток на каждую задачу для команды. Это приводит к необходимости уже на начальном этапе договариваться о стратегии сдачи решений общекомандно и обозначать свою позицию по отношению к каждой задаче внутри команды — берет ли член команды ее на себя, пишет ли варианты решений, или передает ответственность другим.

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

На протяжении всего второго тура на вебинарах поднимаются темы совместных ресурсов (Яндекс.Диск, Github) для структурирования командной работы. На вебинарах не всегда возможно присутствие всех членов команды — и это порождает отдельный процесс по синхронизации информации и понимания. В конце второго тура командам предлагается совместная рефлексия с выявлением слабых и сильных сторон у каждого члена команды, определением белых пятен в знаниях и навыках у каждого и распределением нерешенных задач для дорешивания.

Командные задачи

На заключительном этапе профиля Технологии беспроводной связи будут предложены задачи построения сетей и обеспечения связи в условиях, когда одновременно с ростом числа подключаемых устройств и объемов трафика повышаются требования к надежности и производительности систем.

Прежде всего, второй этап — командный, поэтому оцениваться будет общий результат. Главная цель здесь — формирование команды. Чем лучше будет выстроена командная работа на втором этапе, тем больше шансов на победу будет в каждом из этапов. Обратите внимание на особенность профиля — уже со второго этапа высока роль капитана, от его эффективных действий и распределения функций между членами команды будет зависеть успех выступления команды на втором туре. Общайтесь, учитесь эффективно распределять работу, ищите сильные стороны каждого участника, наращивайте общекомандные навыки — и коммуникативные, и профессиональные. Решайте задачи максимально эффективно и результативно.

Задачи данного этапа знакомят с базовыми концепциями. В них будут затронуты следующие темы:

анализ данных,
кодирование – декодирование,
алгоритмы,
анализ кода,
канал связи,
автономное управление.

Все задачи требуют написания программного кода на одном из следующих языков программирования:

Python 3.12,
Java 17,
C++20,
C17.

Можно работать с любой удобной IDE (Visual Studio Code, Spyder и т. д.) или онлайн-средой (Repl.it, Google Colab и т. д.). Учитывайте, что на платформе Яндекс.Контест во всех языках доступны только стандартные модули без дополнительных библиотек.

Командные задачи второго этапа инженерного тура открыты для решения. Соревнование доступно на платформе Яндекс.Контест: https://contest.yandex.ru/contest/69926/enter/.

Задача 1.1.(10 баллов)

Загадки бумажных болот

Темы: анализ кода, алгоритмы, навык работы с кодировками

Условие

Главному герою фантастической игры Семену не повезло — он застрял в бюрократической параллельной вселенной, в одной далекой стране на альтернативной Земле. В этой стране для регулирования паролей в аккаунтах государственных сервисов используется особая директива — Перечень регламентов утверждения действительности информационной кодировки (ПРУДИК). Каждый государственный сервис каждому новому аккаунту предписывает набор правил ПРУДИКа, по которым пользователю нужно сочинить новый пароль и отправить его бумажной почтой. Чтобы попасть в родную вселенную, Семену предстоит пройти чудовищное испытание — зарегистрироваться на всех онлайн-сервисах и подобрать к ним пароли, соответствующие поставленным правилам Перечня.

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

Пароль должен содержать не менее 5 символов.
Пароль должен содержать арабские цифры.
Пароль должен содержать заглавную букву английского алфавита.
Пароль должен содержать один из специальных символов: ~!@#$%^&*.
Сумма всех арабских цифр в пароле должно равняться 25.
Пароль должен содержать название месяца на английском языке с заглавной буквы.
Сумма всех арабских и римских¹ чисел в пароле должна равняться 35.
Пароль должен содержать римскую цифру.
Перемножение всех римских чисел¹ в пароле должно равняться 35.
Каждое слово² в пароле должно заканчиваться на .py.
Каждое слово должно содержать не более 7 символов.
Пароль не должен содержать пробелов.
Каждое слово должно начинаться с большой буквы.
Пароль должен заканчиваться восклицательным знаком!
Пароль должен начинаться с символа $.
Пароль является палиндромом (без учета пробелов и регистра).
Пароль содержит корректно расставленные скобки: ()[]{}<>.

¹ Римские числа — это непрерывная последовательность римских цифр, приведенных в порядке невозрастания их мощности.

² Слово — это последовательность символов, разделенных одним и более пробелом.

Реализуйте бота, который выполняет проверку соответствия сообщений ПРУДИКу и подсказывает, подходит ли придуманный пароль к очередному сервису.

Формат входных данных

*1,2,3,4 — заявляет набор правил, которые необходимо проверять.
? проверь меня — проверить сообщение на соответствие правилам. Сообщение рассматривается без вопросительного знака и пробела в начале.
# — закончить работу.

Формат выходных данных

NO 1,2,3,4 — ответ на проверку, если сообщение не соответствует правилам. Через запятую приводятся нарушенные правила в порядке возрастания номера.
OK — ответ на все остальные сообщения, в том числе на проверку в случае полного соответствия.

В начале работы система отправляет сообщение и ждет от ответа. Обработав завершающее сообщение, решение должно штатно завершиться.

Тестовые данные

https://disk.yandex.ru/d/BxyK_E8L3mqlEg

Решение

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

Последовательности римских чисел выделяются регулярным выражением, после чего делятся на отдельные числа, основываясь на том, что римское число представляет собой последовательность цифр от большего к меньшему, так как в условии исключено правило вычитания. Например, последовательность XIIVIII будет разделена на числа XII и VIII.

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

Авторское решение на языке Python 3.12 приведено в файле TWC-prudik.py: https://disk.yandex.ru/d/6Ha2By4yMqaKXw.

Критерии оценивания

Это интерактивная задача, значит, программа взаимодействует с проверочной системой посредством стандартных потоков ввода и вывода. Иными словами, после отправки сообщения программа должна очистить буфер (выполнить flush) и считать ответ от системы (прочесть строку). В случае некорректного ответа проверка прерывается с вердиктом PE (Presentation Error).

Задача 1.2.(26 баллов)

Кошмарный писк радиофизика

Темы: канал связи, навык работы с моделями передачи сигнала

Условие

Летучие мыши Порфирий и Настасья мирно жили в уютной пещере и общались между собой ультразвуком. Но в какой-то момент они перестали нормально слышать друг друга — эхо стало оглушительно громким, и различить, где сигнал, а где эхо, уже не получается. Оказаться в кошмарном сне радиофизика неприятно, но нужно выходить из этой ситуации. А так как радиофизик спит беспокойно, но крепко, помогите мышам адаптироваться к новым физическим законам выдуманного мира, а именно: сопоставить передаваемый и принимаемый звук.

Пусть пещера имеет форму выпуклого многоугольника, летучих мышей представим в виде точечных излучателя и приемника. Излучатель передает сигнал в течение 3 с. Прием начинается одновременно с передачей и также длится 3 с. Сигнал проходит по воздуху со скоростью 343 м/с без затухания. Отражение также происходит без затухания, но только один раз. Частота дискретизации составляет 24 кГц. На приемнике принятые сигналы суммируются алгебраическим сложением уровней. Наложением звука на отражение пренебречь. Гарантируется, что излучатель и приемник находятся строго внутри многоугольника. Считать, что сигнал может проходить через излучатель и приемник.

Необходимо написать программу для приемника, которая восстанавливает принятый сигнал.

Формат входных данных

В первой строке — четыре вещественных числа через пробел, пары координат (абсцисса и ордината) излучателя и приемника соответственно. В следующей строке указывается натуральное число $N$, число точек в многоугольнике. Далее идет $N$ строк, в каждой из которых указывается пара вещественных чисел — абсцисса и ордината очередной точки многоугольника. Далее идет 72000 строк, в каждой — вещественное число, значение передаваемого сигнала в условных единицах. Точки многоугольника приводятся по часовой стрелке, все координаты — в метрах.

Формат выходных данных

72000 строк, в каждой — вещественное число, значение принятого сигнала в условных единицах.

Тестовые данные

Номер теста	Стандартный ввод	Стандартный вывод
1	2.5 2.5 -2.5 2.5 4 -5 5 5 5 5 -5 -5 -5 2.811570446214362 35.26305252415367 31.513343289467844 ... 0.0	0.0 0.0 0.0 ... 21.263634409701194 10.45558991528608 13.266212134182132 ... 0.0

Тестовые данные

https://disk.yandex.ru/d/CtNZryVHnW1MUQ.

Решение

Задача решается по следующему алгоритму.

Вычисляем прямое расстояние от передатчика до приемника.
Выясняем для каждой стороны многоугольника, может ли отраженный от передатчика сигнал попасть на приемник, и если да, то какое расстояние придется преодолеть сигналу:
- Строим перпендикуляры от передатчика и приемника до прямой, на которой лежит рассматриваемая сторона многоугольника.
- Проведя отрезок от передатчика до приемника, получим трапецию, составленную из этого отрезка (назовем его верхним основанием), перпендикуляров и отрезка между перпендикулярами (назовем его нижним основанием).
- На нижнем основании должна лежать точка отражения сигнала передатчика в приемник, согласно закону физики: угол отражения равен углу падения.
- Проведя отрезки от передатчика и приемника до точки отражения, получим три треугольника внутри трапеции.
- Известно, что два из трех треугольников являются прямоугольными, а также что углы, образованные точкой отражения, равны (по законам физики). Из этого следует, что они подобны. Благодаря свойствам подобия можно вычислить стороны, разделенные точкой отражения. С помощью значений этих сторон и длин перпендикуляров можно вычислить гипотенузы по теореме Пифагора. Сумма этих гипотенуз является расстоянием, которое сигналу нужно пройти от передатчика до приемника, если он отразится от рассматриваемой стороны многоугольника.
- Так как нижнее основание может выходить за пределы стороны многоугольника, необходимо проверить, что точка отражения действительно лежит на этой стороне. Ее координаты можно вычислить, решив систему уравнений, составленную из уравнения прямой и формулы Евклидова расстояния.
После нахождения длин всех маршрутов от передатчика до приемника определяем значение сигнала, который примет приемник:
- Вычисляем время прихода сигнала до приемника по каждому маршруту.
- Для каждого значения сигнала передатчика вычисляем такт, в который он дойдет по всем маршрутам.
- Складываем сигналы, пришедшие в один и тот же такт. Итоговая сумма сигналов дает ответ.

Авторское решение задачи на языке Python 3.12 приведено в файле TWC-soundroom.py: https://disk.yandex.ru/d/tM6_nIUSCIHNTw.

Критерии оценивания

Решение принимается, если среднее квадратичное отклонение между решением и авторским ответом составит менее 10 условных единиц.

Задача 1.3.(11 баллов)

Работа из-под импульса, подзадача 1

Темы: кодирование – декодирование, навык работы с протоколами, автономное управление

Условие

Белоптичкинский радиолюбительский клуб славится находчивыми специалистами. Недавно они обнаружили, что, скрестив катушку индуктивности, конденсатор и секретный компонент (назначение которого не понимают даже сами изобретатели), можно собрать очень эффективный цифровой приемник, работающий без батареек, чисто на входящем сигнале. Точнее, на восходящих фронтах сигнала (когда значение меняется из нижнего уровня в высокий).

Правда, высокая эффективность дается высокой ценой. Чтобы приемник в принципе начал работать, на него требуется подать 6 восходящих фронтов в течение 15 тактов. Прием сигнала начинается на следующий такт после включающего фронта. Мало того, для поддержки питания необходимо, чтобы за последние 15 тактов было минимум 4 восходящих фронта. В ином случае при очередном такте без фронта приемник выключится, не приняв значение в этом такте. В самом начале на приемнике установлен низкий уровень сигнала.

Дано: тактированный сигнал, который будет передан на приемник. Определите, какое сообщение будет с него получено.

Формат входных данных

Одна строка, произвольное количество нулей и единиц, принимаемый сигнал.

Формат выходных данных

Одна строка, произвольное количество нулей и единиц, считанное сообщение.

Тестовые данные

Номер теста	Стандартный ввод	Стандартный вывод
1	10101010101110100100000110101010101111111101	11010010000011111111101

Тестовые данные

https://disk.yandex.ru/d/mjuIUkZLuIWjFg.

Решение

Для хранения последних 15 значений входной последовательности используем циклический буфер, который изначально заполняем пустыми значениями. Считываем входную последовательность, а затем посимвольно добавляем ее в буфер, считая восходящие фронты и включая/выключая передачу по необходимости.

Считается, что до входной последовательности были нули, поэтому в начале добавляем ноль в последовательность, чтобы учесть восходящий фронт в случае, если последовательность начинается с единицы.

Также учитывается, что ноль, который находится перед обрабатываемыми 15 значениями, может образовывать фронт, если первым значением в буфере является единица.

Авторское решение задачи на языке Python 3.12 приведено в файле TWC-pulsedriver-a.py: https://disk.yandex.ru/d/87dAE18CcbkZqQ.

Задача 1.4.(15 баллов)

Работа из-под импульса, подзадача 2

Темы: кодирование – декодирование, навык работы с протоколами, автономное управление

Условие

Напомним, цифровой приемник включается, когда на него в течение 15 тактов приходит 6 восходящих фронтов. Прием сигнала начинается на следующий такт после включающего фронта и продолжается до тех пор, пока в течение 15 тактов приходит минимум 4 восходящих фронта. В ином случае при очередном такте без фронта приемник выключится, не приняв значение в этом такте. В самом начале на приемнике установлен низкий уровень сигнала.

Теперь решите обратную задачу: спроектируйте такой сигнал, чтобы приемник получил заданную двоичную последовательность.

Формат входных данных

Одна строка, произвольное количество нулей и единиц, передаваемое сообщение.

Формат выходных данных

Одна строка, произвольное количество нулей и единиц, сформированный для передачи сигнал.

Тестовые данные

Номер теста	Стандартный ввод	Стандартный вывод
1	11010010000011111111101	10101010101110100100000110101010101111111101

Тестовые данные

https://disk.yandex.ru/d/b_c9SUX-7OT_Yg.

Решение

Выполняется операция, обратная предыдущей — формируется такой сигнал, чтобы приемник из первой задачи сформировал строку, идентичную ответу. Соответственно, сигнал формируется из входной строки побитово с подсчетом фронтов, как в первой задаче. Если после очередного переданного бита число восходящих фронтов становится меньше необходимого, передается комбинация $01$ в количестве, достаточном для включения, после чего передача возобновляется. Проверка задачи осуществляется программно, поэтому способ включения приемника может быть избыточным и предполагает лишь соответствие условию задачи.

Авторское решение задачи на языке Python 3.12 приведено в файле TWC-pulsedriver-b.py: https://disk.yandex.ru/d/eXWPBbrndnOnFg.

Задача 1.5.(29 баллов)

Не Фурье

Темы: анализ данных, кодирование – декодирование, навык анализа и формирования сигналов

Условие

В Белоптичкинском кружке робототехников готовятся к районной конференции по киберфизике. На один из докладов школьники подготовили робота-попугая, очень похожего на природный прообраз. Умеет даже разговаривать, запоминая и повторяя звуки... Но беда в том, что за полнедели до выступления из строя вышел контроллер, отвечающий за функцию звукоподражания. Юные гении не растерялись и смогли собрать аналогичную схему. Но в ее основе лежит более слабый контроллер, поэтому его дополнили тремя генераторами звука. Осталось написать драйвер.

На его вход передается сигнал длиной до 500 квантов, который необходимо повторить посредством активации трех генераторов в определенном порядке. Для каждого из генераторов известен формируемый им сигнал и время восстановления между завершением генерации и повторной активацией. Все сигналы передаются в квантованном виде с одинаковой частотой дискретизации. Наложение сигналов производится сложением уровней.

Реализуйте описанный драйвер.

Формат входных данных

Четыре блока с передаваемыми данными.

Первый блок — в первой строке натуральное число $N$, длительность сигнала в квантах времени.

Далее идет $N$ строк, в каждой из которых приводится вещественное число, уровень сигнала в соответствующий квант времени.

Следующие три блока устроены одинаково и описывают генерируемые формы сигналов. Первая строка — два натуральных числа $N$ и $M$ через пробел, длительность формы и время восстановления в квантах времени. Далее идет $N$ строк, в каждой из которых приводится вещественное число, уровень генерируемой формы в соответствующий квант времени.

Формат выходных данных

В первой строке — натуральное число $N$, количество активаций генераторов.

Далее идет $N$ строк, в каждой из которых идет пара целых чисел через пробел. Первое число — номер кванта времени (нумерация с 0!), второе — номер активируемого генератора (1, 2, 3).

Тестовые данные

Номер теста	Стандартный ввод	Стандартный вывод
1	48 28.384381050597984 41.03454979919398 64.56745071160744 86.06538001102359 ... 26.94524	5 0 2 9 3 16 1 25 2 32 3

Тестовые данные

https://disk.yandex.ru/d/ja4TN1YJdA0mvQ.

Решение

В основе авторского решения лежит рекурсивный перебор, который заранее исключает неподходящие варианты, за счет чего обеспечивается быстрота решения.

Рекурсивно посмотрим каждый квант заданного сигнала, выполняя следующие действия:

Рассчитать оценку среднеквадратичной невязки между текущим составленным решением и эталонным сигналом.
Если значение оценки превышает 10, то следует рекурсивно вернуться на квант назад и выбрать другой вариант.
Если рассматривается последний квант, и оценка невязки не превышает 10, то это и есть решение, нужно закончить перебор и вывести ответ.
Произвести перебор вариантов запуска генераторов.
Исключить такие варианты, в которых генераторы еще не закончили работу или находятся на восстановлении.
Рассчитать изменения среднеквадратичной невязки для каждого варианта.
Отсортировать варианты по возрастанию оценки среднеквадратичной невязки и выбор варианта с наименьшей невязкой.
Перейти к следующему кванту с учетом выбранного варианта.

Авторское решение задачи на языке Python 3.12 приведено в файле TWC-unfourier.py: https://disk.yandex.ru/d/Zqrtrv9Lf9j8IQ.

Критерии оценивания

Решение принимается с оценкой в 50% за тест, если среднеквадратичная невязка относительно входного сигнала составит не более 50 единиц. Для полного балла необходима невязка не более 10 единиц.

Задача 1.6.(9 баллов)

Кибер-наседка

Темы: автономное управление, навык работы с протоколами и их реализацией

Условие

Следить за чем-то бывает не так просто, а когда следить нужно сразу за многими вещами — здесь справится не каждый. Но можно доверить эту задачу роботам.

На Белоптичкинской птицефабрике проводится работа по технологизации слежки за подрастающими цыплятами. Руководство фабрики обратилось за помощью к местному кружку робототехников, и они собрали «робо-маму». Она круглосуточно отслеживает и различает цыплят с помощью ИИ и машинного зрения.

В прошлом году ребятам удалось «подружить» робота с системой управления птицефабрикой, написанной на языке COBOL задолго до основания кружка. Теперь же умные техники успели съездить на заключительный этап НТО по профилю Технологии беспроводной связи и поняли, как можно улучшить программу и реализовать новый режим работы, необходимый птицефабрике.

Напишите программу-драйвер для обновленной «кибер-мамы», реализующую логику приема и ответа согласно заданному протоколу. Система управления отправляет в драйвер одну из следующих команд:

REMEMBER name priority — добавить в память цыпленка с заданным именем и приоритетом слежения (целое число от 1). Если такой цыпленок уже добавлен, ответить ERROR EXIST, иначе — OK.
FORGET name — удалить цыпленка с заданным именем из памяти. Если такого цыпленка нет в памяти, ответить ERROR MISSING, иначе — OK.
WATCH name — начать следить за цыпленком с заданным именем. Если такой цыпленок не существует, ответить ERROR MISSING, иначе — OK, даже если слежение за цыпленком уже ведется.
UNWATCH name — перестать следить за цыпленком с заданным именем. Если такой цыпленок не существует, ответить ERROR MISSING, иначе — OK, даже если слежение за цыпленком не ведется.
LIST type — перечислить цыплят в алфавитном порядке через запятую с пробелом. Например: 123, CHEEPY3, TAPI. Параметр type задает необходимый список: ALL — вывести всех цыплят в памяти, WATCH — всех, за которыми идет слежка.
ECOMODE priority — включить режим экономии энергии с заданным приоритетом. Приоритет 0 выключает этот режим. Ответить OK.

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

Если переданная команда не соответствует протоколу, следует отвечать ERROR SYNTAX.

Имя цыпленка (name) всегда представляет собой последовательность заглавных латинских букв и цифр. При попытке назвать цыпленка иначе нужно отвечать ERROR NAME в любой команде.

Приоритет всегда является целым положительным числом (0 допустим только в команде ECOMODE). При попытке прописать некорректный приоритет нужно отвечать ERROR PRIORITY.

При выдаче ошибок система отдает приоритет синтаксическим, после параметрическим, и только затем семантическим.

Формат входных данных

Строки с командами, перечисленными в условии.

В одной строке передается только одна команда. Но из-за особенностей драйвера могут встречаться лишние пробелы в начале и конце строки или между словами, а также пустые строки. Их нужно игнорировать.

Формат выходных данных

Строки с ответами на команды в соответствии с условием.

Тестовые данные

Номер теста	Стандартный ввод	Стандартный вывод
1	LIST 874505 REMEMBER LZLH 1893555056 REMEMBER LZLH 400606675 ECOMODE 0 REMEMBER OUMB4 2016754536	ERROR SYNTAX OK ERROR EXIST OK OK

Тестовые данные

https://disk.yandex.ru/d/LJtJbreuMlXR9g.

Решение

Программа считывает входные данные построчно до тех пор, пока не будет встречен маркер конца файла (EOF).

Для хранения записей о цыплятах используется словарь, в котором ключи — имена цыплят, значения — структура со значениями: приоритет и флаг отслеживания цыпленка в данный момент. Логика решения преимущественно реализует операции над словарем. Рекомендуется сортировать ключи словаря в алфавитном порядке. Если структура данных это не предусматривает, можно выделить отдельный массив для хранения сортированных ключей.

Для функции отображения отслеживаемых цыплят выполняем проход по словарю, для каждого цыпленка смотрим приоритет (если включен его учет) и флаг отслеживания.

При считывании команд тщательно проверяется синтаксис команды, наличие аргументов (не больше, не меньше), их корректность. Также учитывается, что могут быть лишние пробелы в строке с командой, причем даже между аргументами.

Авторское решение задачи на языке Python 3.12 приведено в файле TWC-cyber-hen.py: https://disk.yandex.ru/d/rciUWz8R09xS5A.