Инженерный тур. 1 этап
Решите задачу на рис. 1.1 и запишите в ответ, чему равен X — число в десятичной системе счисления.
Пояснение: все символы записаны в позиционной системе счисления, и она одинакова для верхнего и нижнего числа. Другие символы не предусмотрены.
Эта задача проверяет навык работы с математическими моделями и кодировками, что является частью задачи заключительного этапа.
В верхней строчке, слева от знака равенства, пять уникальных символов. Это означает, что сообщение создано в системе счисления с основанием 5 (по числу уникальных символов). При переводе \(1298_{10}\) в систему счисления с основанием 5 получаем \(20143_{5}\).
Сопоставляем символы с получившимся числом: «ананас» — 2, «пицца» — 0, «печенье» — 1, «пончик» — 4, «круассан» — 3. Из этого следует, что в нижней строке слева от знака равенства стоит число \(12340_5\).
Чтобы получить \(X\), необходимо перевести данное число из системы счисления с основанием 5 в десятичную: \(12340_{5} = 970_{10}\). Записываем 970 в ответ.
970.
По восьми каналам связи закодировали и передали двоичные сообщения (рис. 1.2). Для формирования сигнала использовался принцип, очень похожий на манчестерское кодирование. Ниже приведены исходные данные до кодирования, которые передавали в канал, и принятые после прохождения каждого канала сигналы. При передаче по каналу данные могли исказиться, то есть передаться с ошибками. В ответ введите номер канала (только номер, без других символов) с наименьшим искажением данных.
Эта задача проверяет навык анализа кодов и каналов связи, что является частью задачи заключительного этапа.
Манчестерское кодирование представляет собой кодировку двоичного разряда двумя тактами, где значение (ноль или единица) определяется характером изменения уровня между двух тактов. В системе, представленной в задаче, единица кодируется изменением уровня между двух тактов, а ноль — отсутствием изменения. По сути, это дифференциальное манчестерское кодирование со сдвигом на один такт вперед.
Принимая это во внимание, достаточно сопоставить кодируемый сигнал с исходными данными и подсчитать расхождения в каждом из каналов. Выяснится, что в шестом канале будет наименьшее число ошибок (одна).
6
При широком развитии интернета и мобильной связи любительская радиосвязь до сих пор процветает и остается распространенным хобби. Люди с разных концов планеты с помощью собственных радиостанций связываются друг с другом, чтобы пообщаться голосом или обменяться короткими приветствиями на азбуке Морзе.
Невольно с этим хобби соприкоснулся и Алик, найдя на чердаке ламповую радиостанцию и собранную дедушкой телеграфную клавиатуру. Время пощадило технику, но не клей, на котором держались наклейки клавиш — они отпали от клавиатуры и лежали отдельно. В результате поиска и ревизии наклеек выяснилось, что клавиатура может отправлять заглавные латинские символы, цифры, пробел и некоторые знаки препинания (точка, запятая, восклицательный и вопросительный знак).
Алик решил восстановить раскладку клавиатуры. Как смог, он разложил наклейки, после чего стал набирать сообщения и смотреть, что именно отправляет клавиатура. Напишите программу, которая поможет Алику поскорее разобраться с раскладкой.
Задача интерактивная, поэтому программа взаимодействует с проверочной системой посредством стандартных потоков ввода и вывода. Иными словами, после отправки сообщения программа должна очистить буфер (выполнить flush) и считать ответ от системы (прочесть строку).
Итак, программа отправляет сообщение в раскладке Алика и получает в ответ от системы фактически отправленное. Например, программа отправит HELLO I AM ALIK, после должна прочитать строку из потока ввода, где получит, например, URYYB V NZ NYVX. Затем можно вновь отправлять очередное сообщение. Регистр латинских символов важен.
Как только программа восстановит кодировку, она должна отправить сообщение с символом @ в начале и через пробел привести такое сообщение, чтобы на выходе получилось GA DR OM. TKS VY MUCH FR UR CALL. UR RST 599. QTH IRKUTSK. OP IS ALIK. HW?.
В случае правильного итогового ответа программа ответит @ OK, и следует штатно завершить программу. В ином случае проверочная система выставляет WA. Также при наличии в любом сообщении символа не из алфавита задачи (например, строчных букв), проверка посылки завершается досрочно с вердиктом PE.
Например, программа присылает: @ TN QE BZ. GXF IL ZHPU SE HE PNYY. HE EFG 599. DGU VEXHGFX. BC VF NYVX. UJ?. Если это правильный ответ, проверочная система ответит @ OK, иначе завершит программу принудительно.
В пределах каждого теста нужно справиться с восстановлением кодировки не более, чем за 20 запросов. Если больше — решение отклоняется с WA. Если участник справился за минимально возможное число запросов, он получит за соответствующий тест максимальный балл, в противном случае — лишь половину.
Эта задача проверяет навык анализа кодировки, что является частью задачи заключительного этапа.
Примечания
- Каждое входящее и исходящее сообщение должно заканчиваться переносом строки.
Очистка буфера делается следующим образом:
fflush(stdout)в C;fflush(stdout)илиcout.flush()в C++;sys.stdout.flush()в Python;System.out.flush()в Java.
Формат входных данных
Строки, состоящие из заглавных латинских символов, цифр, пробелов, точек, запятых, восклицательных и вопросительных знаков. Если отправляется итоговый ответ, строка должна начинаться со знака @ и пробела.
Формат выходных данных
Строки аналогичного формата.
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
HELLO I AM ALIK @ TN QE BZ. GXF IL ZHPU SE HE PNYY. HE EFG 599. DGU VEXHGFX. BC VF NYVX. UJ? |
URYYB V NZ NYVX @ OK |
Тестовые данные
В задаче представлен тривиальный шифр замены с нестандартным алфавитом. Необходимо восстановить алфавит замены. Это можно сделать одним сообщением, содержащим полный алфавит: «ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 .,!?». Получив ответ от проверочной системы, нужно сопоставить символ сообщения с символом отправленного алфавита и сформировать итоговую посылку, ориентируясь на эти сопоставления.
Ограничение на 20 посылок в условии для частичного решения — намеренно оставленная ловушка.
Авторское решение задачи на языке Python 3.12 представлено по ссылке: https://disk.yandex.ru/d/mSJEPZJZqp6MKw.
Следить за чем-то бывает не так просто, а когда следить нужно сразу за многими вещами — здесь справится не каждый. Но можно доверить эту задачу роботам.
На Белоптичкинской птицефабрике проводится работа по технологизации слежки за подрастающими цыплятами. Руководство фабрики обратилось за помощью к местному кружку робототехников, и они собрали «робо-маму». Она круглосуточно отслеживает и различает цыплят с помощью ИИ и машинного зрения. Не хватало лишь одной немаловажной части — «подружить» робота с системой управления птицефабрикой, написанной на языке COBOL задолго до основания кружка.
Напишите программу-драйвер для «робо-мамы», реализующую логику приема и ответа согласно заданного протокола. Система управления отправляет в драйвер одну из следующих команд:
REMEMBER name— добавить в память цыпленка с заданным именем. Если такой цыпленок уже добавлен, ответить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— всех, за которыми идет слежка.
Имя цыпленка (name) всегда представляет собой последовательность заглавных латинских букв и цифр. При попытке назвать цыпленка иначе нужно отвечать ERROR NAME в любой команде. Если переданная команда не соответствует протоколу, следует отвечать ERROR SYNTAX.
Эта задача проверяет навык работы с протоколами и их реализацией, что является частью задачи заключительного этапа.
Формат входных данных
Последовательность строк (до 200), в каждой из которых приведена отдельная команда.
Формат выходных данных
Такое же число строк, в каждой из которых приводится ответ на соответствующую команду.
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
WATCH D0KOP98Y WATCH z WATCH gejb WATCH W9S REMEMBER 31K882IR WATCH 31K882IR WATCH 4S9C9Q8 WATCH 31K882IR WATCH 31K882IR WATCH 31K882IR ... |
ERROR MISSING ERROR NAME ERROR NAME ERROR MISSING OK OK ERROR MISSING OK OK OK ... |
Тестовые данные
Задача предполагает прямолинейную реализацию заданного протокола и интерпретацию всех переданных во входных данных команд, в том числе ошибочных (очень важно разделять ошибки формата имени и формата сообщения). Для хранения информации о цыплятах предлагается использовать структуру типа «словарь».
Авторское решение задачи на языке Python 3.12 представлено по ссылке: https://disk.yandex.ru/d/BfINPEVtKYTKfQ .
Передавать изображения на расстояние научились сравнительно недавно, в конце XIX века, а первые телевизоры просуществовали недолго, быстро уступив место более привычным электронно-лучевым трубкам. Но идея, лежащая в основе первых телевизоров, проста и интересна, и такой телевизор можно собрать своими руками (например, как в этой статье: https://nplus1.ru/material/2021/12/01/nipkow-avito).
Представим механический телевизор Б-2 на основе диска Нипкова, рассчитанного на отображение кадра в 30 строк с частотой 12,5 кадров в секунду. В телевизор передается двоичный сигнал частотой 22,5 кГц, задающий яркость светодиода (соответственно, в двух значениях — максимальная и минимальная).
Предлагается файл (https://disk.yandex.ru/d/VJHdZns97iwaLg) с сигналом, передаваемым в такой телевизор. Обусловимся, что прием сигнала начинается одновременно с движением самой верхней прорези от левого угла кадра, вращение идеально синхронизировано с передаваемым сигналом, а трапециевидным искажением изображения можно пренебречь.
Восстановите сообщение, содержащееся в видеоизображении, и приведите его в ответе. Оно состоит из букв русского алфавита и знаков препинания. Регистр важен.
Чтобы файл не был таким большим, дублирующие кадры удалены, а сигнал сжат с помощью алгоритма RLE. Для наглядности в качестве максимальной и минимальной яркости используются символы «*» и «.» соответственно. Так, 3*1.3*2. будет декодировано в ***.***..
Эта задача проверяет навык работы с кодировками и особенностями канала связи, что является частью задачи заключительного этапа.
RLE — способ сжатия через кодирование непрерывно повторяющихся последовательностей. Следовательно, для декодирования необходимо продублировать символы «*» и «.» указанное число раз. Для простоты решено не использовать отрицательные индексы, кодирующие неповторяющиеся последовательности.
Далее замечаем, что в задаче идет речь о строчной развертке сигнала. Так как частота передачи составляет 12,5 кадров в секунду при 30 строках, всего за секунду передается 375 строк. Частота входного двоичного сигнала указывает на число измерений в секунду, которое составляет 22500 Гц. Поделив это число на 375, получаем 60 — это горизонтальное разрешение, то есть число точек изображения (и соответственно символов) в одной строке.
Следовательно, разрешение кадра составляет 60 на 30 точек. Зная это, можно разбить декодированную по RLE последовательность символов на строки по 60 символов и отделить последовательности по 30 строк, формируя цепочку кадров. Получение искомого текста из нее осуществляется визуально.
Сообщение: «Радио — это улей, в котором слышится жужжание всего мира!».
