Автор Задания, ответы и разбор заключительного этапа ВОШ 2021 по информатике для 9, 10, 11 класса всероссийской олимпиады школьников, официальная дата проведения олимпиады: 07.04.2021-13.04.2021 (с 7 апреля по 13 апреля 2021 год)
Ссылка для скачивания заданий 1 тура для 9-11 класса: скачать
Ссылка для скачивания заданий 2 тура для 9-11 класса: скачать
Ссылка для скачивания ответов и разбора заданий 1 тура: скачать
Ссылка для скачивания ответов и разбора заданий 2 тура: скачать
Результаты заключительного этапа 2021 по информатике: скачать
Заключительный этап 2021 олимпиады по информатике 9-11 класс задания и ответы 1 тура:
Заключительный этап 2021 олимпиады по информатике 9-11 класс задания и ответы 2 тура:
Интересные задания с олимпиады заключительного этапа 2021:
1)На складе фирмы, на базе которой проходит олимпиада по программированию, были обнаружены n перфокарт. Перфокарта представляет собой полоску из m клеточек, каждая из которых либо содержит строчную английскую букву, либо является отверстием. Жюри олимпиады решило упорядочить все перфокарты так, что если расположить их одну под другой сверху вниз в этом порядке, то получится лозунг олимпиады — заданная строка s длины m. Иными словами, зафиксируем порядок перфокарт, в котором они будут лежать, и рассмотрим произвольную позицию i (1 6 i 6 m). Тогда i-й символ строки s должен совпадать с символом на i-й позиции самой верхней перфокарты, содержащей на позиции i какую-либо букву. Если для какого-то i ни одной перфокарты с буквой в позиции i нет, то считается, что требуемую строку s получить невозможно. Помогите жюри понять, в каком порядке необходимо расположить перфокарты.
2)Вы играете на смартфоне в игру «Родные просторы», в которой управляющий Остап помогает помещику восстановить отцовский дом. Игра происходит следующим образом. Дана последовательность из n кристаллов, расположенных в один ряд слева направо. Каждый кристалл относится к одному из k видов, обозначенных первыми k английскими буквами. Таким образом, последовательность кристаллов записывается строкой английских букв. За один ход игры можно удалить из последовательности один кристалл. Цель игрока — получить в результате применения разрешенных видов удалений лексикографически минимально возможную строку. Разрешённые виды удаления кристаллов заданы таблицей A размера k × k из нулей и единиц. Если Aij = 1, то разрешается удалить кристалл вида j, если непосредственно слева от него находится кристалл вида i. Данные действия можно выполнять в любом порядке.
3)Это интерактивная задача с двойным запуском. Один шпион добыл важное сообщение, и ему необходимо передать его в центр. Так как сообщение важное, было решено, что необходимо скрыть даже сам факт передачи какой-либо информации, и поэтому передача сообщения будет замаскирована под стрим набирающей популярность игры «Щёлк». Правила игры «Щёлк» очень простые. На квадратном поле размера n × n изначально ни одна клетка не закрашена. Два игрока ходят по очереди. За один ход игрок может выбрать любую ещё незакрашенную клетку и закрасить её и все незакрашенные клетки прямоугольника, левым нижним углом которого является выбранная клетка, а правым верхним — правый верхний угол поля (см. рисунок). Игрок, закрасивший левый нижний угол поля, проигрывает. Шпион будет играть на сайте, предоставляющем возможность сыграть с ботом. Бот играет следующим образом: каждый раз он случайно равновероятно выбирает один из ходов, которые закрашивают не более k новых клеток, кроме хода в левый нижний угол. Если же ход в левый нижний угол — единственный оставшийся, то бот делает его и проигрывает игру. Шпион может сыграть столько игр, сколько необходимо, однако для целей конспирации лучше, чтобы их было как можно меньше. Кроме того, чтобы все выглядело как можно менее подозрительно, лучше как можно больше игр выиграть. С помощью записи ходов, сделанных во всех сыгранных играх, шпион и планирует передать важное сообщение. Вам необходимо написать программу, которая будет запущена два раза. При первом запуске программа будет исполнять роль шпиона: зная секретное сообщение, она сыграет с ботом несколько игр в «Щёлк», а при втором запуске, получив только списки ходов этих игр, восстановит секретное сообщение.
4)В компании работают n бурундуков (n > 2), пронумерованных целыми числами от 1 до n. Бурундук с номером 1 является основателем компании, а каждый из остальных бурундуков имеет ровно одного непосредственного начальника. Иными словами, иерархия бурундуков представляет собой корневое дерево, где родитель вершины является её начальником, а дети вершины являются её подчинёнными. Бурундуки, имеющие подчинённых, называются менеджерами, а остальные — консультантами. Структура компании такова, что каждый менеджер имеет не более 8 подчинённых. Обратите внимание, что основатель компании также является менеджером. Основатель компании решил составить доклад для инвесторов о последних проделанных улучшениях разрабатываемого продукта. Каждое улучшение является результатом работы кого-то из консультантов компании. Все улучшения пронумерованы в хронологическим порядке их совершения. Для каждого из консультантов известен список улучшений, сделанных этим консультантом. Каждый консультант обязан выбрать одно из этих улучшений и сделать о нём доклад своему менеджеру. Таким образом, доклад любого консультанта будет состоять ровно из одного улучшения. Каждый менеджер, в том числе основатель компании, должен сделать доклад, представляющий собой объединение докладов всех его подчиненных. Для этого он берёт доклады, полученные от подчинённых, и записывает их подряд без изменений в некотором порядке. Например, если первый доклад состоит из улучшений [1, 3], а второй — из улучшений [2, 4, 10], то в результате объединения может получиться доклад [2, 4, 10, 1, 3], либо доклад [1, 3, 2, 4, 10], никакие другие доклады получиться не могут. Основатель компании стремится рассказать об улучшениях максимально логично, поэтому он хочет, чтобы в его докладе улучшения шли в хронологическом порядке, то есть по возрастанию номеров. Помогите консультантам выбрать, о каком улучшении они должны рассказать, а менеджерам выбрать, в каком порядке им располагать доклады подчиненных при объединении, чтобы в итоговом докладе основателя компании вошедшие в него улучшения шли в хронологическом порядке.
5)Скорее всего, вы знакомы с римскими числами. А также наверняка слышали фразу, что Москва — это третий Рим. Поэтому мы решили по аналогии с римскими числами придумать их продвинутую версию — московские числа. Цифрами московского числа являются заглавные английские буквы от A до Z. Числом является строка из нескольких цифр. Каждой цифре сопоставим значение. Значение числа равно сумме вкладов цифр, из которых оно состоит. Вклад цифры бывает как положительным, так и отрицательным. Если правее цифры в числе нет строго большей цифры, то вклад этой цифры равен её значению. Иначе вклад равен её значению, взятому со знаком минус.
6)Вася недавно придумал новое развлечение. Пусть дан связный ориентированный граф, состоящий из n вершин и 2 ·(n−1) рёбер, причём для каждого ребра (u, v), существует ребро (v, u). Иначе говоря, граф был получен из дерева, в котором каждое ребро было расщеплено на два противоположных ребра, ориентированных в разные стороны. Назовем гаджетом такую пару рёбер (e1, e2), что конец e1 совпадает с началом e2 или наоборот (в частности, два противоположных друг другу ребра — гаджет). Вася развлекается тем, что разбивает рёбра графа на непересекающиеся гаджеты. Конечно, ему легко удалось это сделать с исходным графом. Васин друг Петя удалил из дерева 2·k ориентированных рёбер. Таким образом, в графе осталось m = 2 · (n − 1) − 2 · k ориентированных ребер. Теперь Вася хочет узнать, можно ли разбить оставшиеся ребра на непересекающиеся гаджеты, и, если можно, — найти это разбиение. Помогите ему!
7)Организация «2Д» занимается выдачей разрешений на вырубку леса. Ей поступают заявки на вырубку деревьев, расположенных вдоль шоссе. На шоссе расположены n деревьев, i-е из них растёт в точке с координатой xi и имеет высоту hi . Информация про имеющиеся деревья упорядочена так, что выполняется x1 < x2 < . . . < xn−1 < xn. Деревья можно вырубать по одному следующим образом. Дерево срубается под корень и затем должно быть повалено либо влево, либо вправо. Чтобы дерево не повредилось при падении, оно не должно задевать ещё не срубленные деревья на расстоянии меньше своей высоты. Иначе говоря, если дерево в точке xi высоты hi валят направо, то не должно быть еще не срубленного дерева с координатой xj такой, что xi < xj < xi + hi . Если это же дерево валят налево, то не должно быть еще не срубленного дерева с координатой xj такой, что xi − hi < xj < xi . Слева от дерева с координатой x1 и справа от дерева с координатой xn находятся важные постройки, поэтому валить деревья так, чтобы они падали за пределы отрезка [x1, xn] запрещается. Иначе говоря, дерево в точке xi высоты hi нельзя валить влево, если xi − hi < x1, и нельзя валить вправо, если xi + hi > xn.
8)Ян и Татьяна решили стать блогерами-путешественниками и публиковать ролики о поездках по городам своей страны. В стране есть n городов, пронумерованных от 1 до n. Город 1 — столица их страны. Города соединены m двусторонними дорогами, пронумерованными от 1 до m, каждая из которых соединяет два различных города. При этом одну и ту же пару городов могут соединять несколько различных дорог. Из любого города по дорогам можно доехать до любого другого города страны. Ребята планируют выложить ролики на известную платформу, где большей популярностью пользуются короткие ролики, поэтому они хотят минимизировать суммарную длину двух роликов. Чтобы выбрать конечный город и маршрут для путешествия, блогеры хотят для каждого конечного города k подсчитать минимальную по всем возможным маршрутам из города 1 в город k суммарную длину двух роликов.
Смотрите также на нашем сайте олимпиады ВОШ:
ВСЕРОССИЙСКИЕ олимпиады 2021 заключительный этап задания и ответы