Компания flatland dynamics разрабатывает прыгающего робота

Задача A2. Прыгающий робот
≡

Условие

Компания «Flatland Dynamics» разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из n специальных платформ, пронумерованных от 1 до n. Расстояние между i-й и i + 1-й платформой равно d_i, аналогично расстояние между n-й и 1-й платформой равно d_n.

Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью — целым числом a. Робот может перепрыгнуть с платформы i на платформу i + 1, если a ≥ d_i. Аналогично, прыжок с n-й платформы на 1-ю возможен, если a ≥ d_n. При этом после каждого прыжка ловкость робота увеличивается на~1.

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

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

На первой строке ввода находится число n (3 ≤ n ≤ 10⁷).

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

Если f = 1, то на третьей строке находятся n целых чисел d₁, d₂, …, d_n (1 ≤ d_i ≤ 10⁹).

Если f = 2, то на третьей строке находится число m (2 ≤ m ≤ min(n, 10⁵)) и три целых числа x, y и z (0 ≤ x, y, z ≤ 10⁹). На четвертой строке находятся m целых чисел c₁, c₂, …, c_m (1 ≤ c_i ≤ 10⁹). Значения d_i вычисляются по следующим формулам.

Если 1 ≤ i ≤ m, то d_i = c_i.

Если m + 1 ≤ i ≤ n, то d_i = ((x ⋅ d_i − 2 + y ⋅ d_i − 1 + z) mod 10⁹) + 1.

Здесь  mod  означает остаток от целочисленного деления, в языках C++, Java и Python он обозначается символом «%».

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

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

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

Ограничения

Система оценки

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

Пояснение к примеру

Во втором примере массив расстояний между платформами равен [1, 2, 3, 4, 5, 18, 45, 112, 273, 662]. Значения от d₆ до d₁₀ вычисляются по формулам:

d₆ = ((1 ⋅ d₄ + 2 ⋅ d₅ + 3) mod 10⁹) + 1 = ((1 ⋅ 4 + 2 ⋅ 5 + 3) mod 10⁹) + 1 = 18

d₇ = ((1 ⋅ d₅ + 2 ⋅ d₆ + 3) mod 10⁹) + 1 = ((1 ⋅ 5 + 2 ⋅ 18 + 3) mod 10⁹) + 1 = 45

d₈ = ((1 ⋅ d₆ + 2 ⋅ d₇ + 3) mod 10⁹) + 1 = ((1 ⋅ 18 + 2 ⋅ 45 + 3) mod 10⁹) + 1 = 112

d₉ = ((1 ⋅ d₇ + 2 ⋅ d₈ + 3) mod 10⁹) + 1 = ((1 ⋅ 45 + 2 ⋅ 112 + 3) mod 10⁹) + 1 = 273

d₁₀ = ((1 ⋅ d₈ + 2 ⋅ d₉ + 3) mod 10⁹) + 1 = ((1 ⋅ 112 + 2 ⋅ 273 + 3) mod 10⁹) + 1 = 662

Примеры тестов

5
1
3 7 4 2 5

4 3

10
2
5 1 2 3
1 2 3 4 5

653 1

Региональный этап 2022 по информатике 9, 10, 11 класс официальные ответы, задания и разбор задач всероссийской олимпиады школьников ВСОШ, официальная дата проведения олимпиады: 15-17 января 2022 года.

Задания олимпиады: 1 тур, 2 тур

Ответы для заданий: скачать

Архив с тестами: скачать

Региональный этап 2022 олимпиады по информатике 9-11 класс задания и ответы:

2 тур олимпиады:

Задача 1. «Чемпионат по устному счету», разбор

Задача 2. «Прыгающий робот», разбор

Задача 3. «Треугольная головоломка», разбор

Задача 4. «Массивы-палиндромы», разбор

Задача 5. «Новый год в детском саду», разбор

Задача 6. «Сортировка дробей», разбор

Задача 7. «Оптические каналы связи», разбор

Задача 8. «Подарки», разбор



1)Председатель жюри чемпионата по устному счету придумал новое задание для участников чемпионата. Исходно на доске выписывается n целых чисел: a1, a2, . . . , an. После этого участник должен выполнять команды двух типов: 1. Стереть i-е число с доски и записать вместо него число x. То есть, если на доске были записаны числа a1, a2, . . . , an, то после выполнения команды числа будут равны: a1, . . . , ai−1, x, ai+1, . . . , an. 2. Циклически сдвинуть последовательность чисел на k вправо. То есть, если на доске были записаны числа a1, a2, . . . , an, то после выполнения команды числа будут равны: an−k+1, an−k+2, . . . , an, a1, a2, . . . , an−k. После выполнения каждой команды участник должен вычислить сумму всех чисел, записанных на доске, и сообщить ее жюри. Чтобы подготовиться проверять ответы участников, членам жюри необходимо самим вычислить требуемые суммы.

2)Компания «Flatland Dynamics» разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из n специальных платформ, пронумерованных от 1 до n. Расстояние между i-й и i + 1-й платформой равно di , аналогично расстояние между n-й и 1-й платформой равно dn. Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью — целым числом a. Робот может перепрыгнуть с платформы i на платформу i+1, если a ⩾ di . Аналогично, прыжок с n-й платформы на 1-ю возможен, если a ⩾ dn. При этом после каждого прыжка ловкость робота увеличивается на 1. Разработчики робота выбирают одну из платформ в качестве стартовой. Они считают эксперимент удачным, если робот может, совершив n прыжков от текущей платформы к следующей, завершить полный круг и вернуться на ту же платформу. Разработчикам необходимо выяснить, для какого минимального значения начальной ловкости робота им удастся провести эксперимент и с какой платформы роботу следует начать прыжки.

3)Головоломка состоит из n треугольников. Чтобы решить головоломку, необходимо выбрать из них четыре треугольника и собрать из них большой треугольник по следующей схеме: треугольники не должны пересекаться, в объединении они должны давать треугольник. Ровно по одному из выбранных треугольников должны находиться в углах, а один треугольник должен располагаться в центре. Треугольники лежат на столе, их можно свободно вращать и двигать, но нельзя зеркально отражать. Требуется найти все различные наборы из четырех треугольников, из которых можно собрать большой треугольник по указанной схеме. Два набора считаются разными, если существует треугольник, входящий в один, но не входящий в другой.

4)Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: A = [a1, a2, . . . , an] длины n и B = [b1, b2, . . . , bm] длины m. Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как A′ и B′ , а их длину как k. Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как C = [c1, c2, . . . , ck]. Пусть, например, n = 5, A = [4, 3, 3, 2, 1], m = 6, B = [4, 1, 5, 1, 3, 2], от массива A отбрасывается первый и последний элемент, от массива B три первых. После этого массивы имеют вид A′ = [3, 3, 2], B′ = [1, 3, 2], результат их поэлементного суммирования C = [4, 6, 4]. Задача Кая заключается в том, чтобы получать такие C, которые являются массивами палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех i числа на позициях i и k−i+ 1 совпадают. Помогите Каю понять, какой максимальный по длине массив-палиндром он может получить в результате эксперимента.

5)В детском саду готовятся к новому году, и воспитательница решила организовать детей, чтобы они подготовили украшения и отправили их Санте Клаусу для украшения своих оленей. Дети с интересом восприняли идею и вырезали из бумаги a звездочек и b снежинок. Теперь они планируют отправить их Санте Клаусу по почте. Им так понравились вырезанные ими украшения, что они, возможно, решат оставить себе часть. Таким образом, дети могут отправить Санте x звездочек и y снежинок, где 0 ⩽ x ⩽ a и 0 ⩽ y ⩽ b. Чтобы Санта не расстроился, дети должны отправить ему хотя бы одно украшение. То есть должно выполняться также условие x + y > 0. Чтобы все олени выглядели красиво, на каждом должно оказаться одинаковое количество украшений. Известно, что у Санты n оленей, поэтому если будут отправлены x звездочек и y снежинок, величина x + y должна делиться на n. Воспитательница заинтересовалась: а сколько есть всего различных способов составить посылку Санте Клаусу. Два способа считаются различными, если в них отличается количество звездочек или количество снежинок.

6)На доске выписано две последовательности из n различных целых чисел: A = [a1, a2, . . . , an] и B = [b1, b2, . . . , bn]. Составим из них n 2 дробей вида ai/bj , сократим каждую дробь и отсортируем их по неубыванию. Задано число q и q целых чисел c1, c2, . . . , cq. Для каждого j следует выдать cj -ю в неубывающем порядке дробь из получившихся.

7)Всего во Флатландии n городов, пронумерованных от 1 до n, столица Флатландии имеет номер 1. Компьютерная сеть Флатландии устроена следующим образом: в каждом городе есть один центр подключения, который может быть связан с некоторыми другими центрами с помощью проводных каналов связи. При этом между любыми двумя городами есть ровно один маршрут по каналам связи, иначе говоря, сеть представляет собой дерево. Для города i, где i > 1, обозначим первый город на маршруте от города i до столицы как pi . Запланирована модернизация сети Флатландии, в результате которой некоторые каналы связи будут заменены на более современные оптические. Оптические каналы могут быть проложены только вместо существующих проводных. Стоимость замены канала, который соединяет город i с городом pi , равна wi . Из-за ограничений технологии любой центр подключения может быть непосредственно подключен оптическими каналами не более чем к k другим центрам. Министерство связи Флатландии хочет составить такой план модернизации каналов, чтобы после его выполнения связность сети по оптическим каналам связи была как можно выше. Поэтому необходимо выбрать для модернизации как можно больше каналов. Но при этом стоимость модернизации желательно минимизировать, поэтому при равном количестве необходимо выбрать для модернизации каналы с минимальной суммарной стоимостью. Помогите специалистам министерства выбрать каналы для модернизации.

8)Дед Мороз предлагает Вове выбрать подарки на Новый год. Перед мальчиком лежат n подарков в ряд. Каждый подарок характеризуется целым числом, у i-го подарка оно равно ai — количество удовольствия, которое подарок принесёт Вове. Удовольствие может быть как положительным, так и отрицательным, а также равным нулю. Дед Мороз предложил Вове выбрать два числа l и r таких, что 1 ⩽ l ⩽ r ⩽ n, и взять все подарки с номерами от l до r. Однако k подарков с максимальными характеристиками среди выбранных Вова должен отдать своей младшей сестре Маше. Остальные подарки Вова забирает себе. Вова хочет выбрать числа l и r так, чтобы суммарное удовольствие от подарков, доставшихся именно ему, было максимальным. Общее удовольствие от набора подарков — это сумма значений ai для подарков в наборе. Помогите Вове выбрать числа l и r так, что 1 ⩽ l ⩽ r ⩽ n, r − l + 1 ⩾ k и общее удовольствие от выбранных подарков без учёта подарков, доставшихся Маше, максимально.

Смотрите также на нашем сайте другие предметы:

Региональный этап 2021-2022 всероссийской олимпиады школьников задания и ответы

Региональный этап ВОШ 2021 по информатике 9-11 класс задания и ответы

ПОДЕЛИТЬСЯ МАТЕРИАЛОМ

Принципы биомиметики

Команда магистрантов факультета систем управления и робототехники — Кирилла Насонова и Дмитрия Волянского — под руководством научного сотрудника ИТМО Ивана Борисова работает над созданием галопирующего робота с уникальными морфологическими характеристиками. Главная задача команды — разработать такую конструкцию, которая одновременно будет легкой, эластичной, энергоэффективной и при этом функциональной. Для этого используются принципы биомиметики и морфологического расчета.

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

Иван Борисов, научный сотрудник Университета ИТМО:

«Наша задача состоит в разработке методов проектирования роботов, способных работать в условиях неструктурированной и неизвестной среды. В качестве платформы для апробации методов и принципов проектирования мы разрабатываем галопирующего робота, способного быстро и энергоэффективно перемещаться. Современные шагающие или галопирующие роботы, например Spot или Unitree, в основном представляют собой такую “табуретку на ножках” — это абсолютно жесткое тело с ногами открытой кинематики. Они показали свою эффективность: они действительно могут ходить, бегать, взбираться на лестницы и даже крутить сальто, но они тратят очень много электроэнергии. Бег — это периодическое движение.

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

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

Морфологическое проектирование

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

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

«Основным актуатором в этой системе является пружина растяжения: при падении робота она растягивается и накапливает потенциальную энергию, а при отскоке эта запасенная энергия преобразуется обратно в кинетическую энергию. Таким образом, происходит рекуперация энергии, а работа двигателя сводится к компенсированию потерь энергии на удар и трение», — объясняет Иван Борисов.

Гибкие элементы

Кроме того, для достижения высокой энергоэффективности потребовалось максимально облегчить корпус робота — избавиться от тяжелых элементов конструкции: зубчатых колес, металлических осей и подшипников. Для решения второй задачи были применены результаты исследований университета-партнера ИТМО — Университета Твенте.

«У нас была теория про гибкие сочленения — они могут совершать поворот на определенный угол, при этом они легкие, у них отсутствуют трения и люфты. Встал вопрос о том, как это вообще проектировать. Сама задача проектирования сочленений является нетривиальной — мы не можем просто взять, допустим, пластик и соединить его под каким-то углом — это все рассчитывается математически. В Университете Твенте есть лаборатория, которая этим занимается. И, к счастью для нас, их труды являются открытыми. Мы можем посмотреть, как они это делают, и на основе этого получить свое решение», — рассказывает Кирилл Насонов.

В Университете Твенте, в лаборатории Дэниса Броуэра, синтезируют механизмы с гибкими сочленениями преимущественно для обеспечения высокоточного движения. В проекте Университета ИТМО механизм с гибкими элементами был синтезирован для обеспечения силового взаимодействия механизма с окружением. Сочленения были напечатаны на трехмерном принтере из полиуретана, гибкого пластика с тянущейся структурой. Сочленения имеют трехлистную геометрическую форму — именно она обеспечивает необходимые параметры упругости, прочности и стойкости к деформациям.

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

Прототип для тестирования

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

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

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

К началу

Профессор и инженер Эллиот Хоукс вместе с коллегами создал устройство, которое прыгает на 30-метровую высоту.

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

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

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

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

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

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

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

Читать далее

Посмотрите в прямом эфире, как астероид размером с автобус приближается к Земле             

Астрономы нашли планету недалеко от Земли: у нее очень странная орбита

За ней охотились столетиями: что нам известно о планете Вулкан рядом с Солнцем