ВОШ Заключительный этап ответы и задания для 9, 10, 11 классов олимпиады по Информатике заключительный этап 2020-2021 всероссийской олимпиады школьников (ВсОШ). Олимпиада проходит во всех школах регионах России с 06 — 11 апреля
Скачать задания день 1 + Решения
Скачать задания день 2 + Решения
Смотреть Онлайн День 1
Смотреть Онлайн День 2
Интересные задания:
Задача 2. Родные просторы
Вы играете на смартфоне в игру ¾Родные просторы¿, в которой управляющий Остап помогает помещику восстановить отцовский дом. Игра происходит следующим образом.
Дана последовательность из n кристаллов, расположенных в один ряд слева направо. Каждый кристалл относится к одному из k видов, обозначенных первыми k английскими буквами. Таким образом, последовательность кристаллов записывается строкой английских букв.
За один ход игры можно удалить из последовательности один кристалл. Цель игрока получить в результате применения разрешенных видов удалений лексикографически минимально возможную строку.
Разрешённые виды удаления кристаллов заданы таблицей A размера k × k из нулей и единиц. Если Aij = 1, то разрешается удалить кристалл вида j, если непосредственно слева от него находится кристалл вида i. Данные действия можно выполнять в любом порядке.
Напомним, что строка x лексикографически меньше строки y, если выполнено одно из двух условий:
–существует такая позиция символа m, присутствующая в обеих строках, что до m-го символа строки совпадают, а m-й символ строки x меньше m-го символа y,
–строка x является строгим префиксом y (то есть получается отбрасыванием одного или боль-ше символов с конца строки y).
Задача 4. Доклад инвесторам
В компании работают n бурундуков (n > 2), пронумерованных целыми числами от 1 до n. Бу-рундук с номером 1 является основателем компании, а каждый из остальных бурундуков имеет ровно одного непосредственного начальника. Иными словами, иерархия бурундуков представляет собой корневое дерево, где родитель вершины является её начальником, а дети вершины являются её подчинёнными. Бурундуки, имеющие подчинённых, называются менеджерами, а остальные кон-сультантами. Структура компании такова, что каждый менеджер имеет не более 8 подчинённых. Обратите внимание, что основатель компании также является менеджером.
Основатель компании решил составить доклад для инвесторов о последних проделанных улучше-ниях разрабатываемого продукта. Каждое улучшение является результатом работы кого-то из кон-сультантов компании. Все улучшения пронумерованы в хронологическим порядке их совершения.
Для каждого из консультантов известен список улучшений, сделанных этим консультантом. Каждый консультант обязан выбрать одно из этих улучшений и сделать о нём доклад своему мене-джеру. Таким образом, доклад любого консультанта будет состоять ровно из одного улучшения.
Каждый менеджер, в том числе основатель компании, должен сделать доклад, представляющий собой объединение докладов всех его подчиненных. Для этого он берёт доклады, полученные от подчинённых, и записывает их подряд без изменений в некотором порядке. Например, если первый доклад состоит из улучшений [1, 3], а второй из улучшений [2, 4, 10], то в результате объединения может получиться доклад [2, 4, 10, 1, 3], либо доклад [1, 3, 2, 4, 10], никакие другие доклады получить-ся не могут.
Основатель компании стремится рассказать об улучшениях максимально логично, поэтому он хочет, чтобы в его докладе улучшения шли в хронологическом порядке, то есть по возрастанию но-меров. Помогите консультантам выбрать, о каком улучшении они должны рассказать, а менеджерам выбрать, в каком порядке им располагать доклады подчиненных при объединении, чтобы в итоговом докладе основателя компании вошедшие в него улучшения шли в хронологическом порядке.
Задача 8. Блогеры-путешественники
Ян и Татьяна решили стать блогерами-путешественниками и публиковать ролики о поездках по городам своей страны.
В стране есть n городов, пронумерованных от 1 до n. Город 1 столица их страны. Города соединены m двусторонними дорогами, пронумерованными от 1 до m, каждая из которых соединяет два различных города. При этом одну и ту же пару городов могут соединять несколько различных дорог. Из любого города по дорогам можно доехать до любого другого города страны.
Путешественники планируют отправиться из столицы в какой-то другой город, но пока не вы-брали в какой. Маршрут путешествия в город k будет состоять из городов s1, s2, . . . , sq и дорог
r1, r2, . . . , rq−1, таких что: – s1 = 1, sq = k;
–дорога ri соединяет города si и si+1;
–ребята не проезжают по одной и той же дороге дважды, поэтому все ri различны. Допус-
кается проезжать несколько раз через один и тот же город, в том числе через город 1, где путешествие начинается, и город k, в котором путешествие заканчивается.
Для каждой дороги Ян и Татьяна посчитали длительность ролика, который получится при съем-ке путешествия по этой дороге, длительность ролика для дороги с номером i равна ti.
В процессе путешествия каждый из ребят выберет одну из дорог маршрута и снимет ролик, по-свящённый этой дороге. При этом Ян любит снимать короткие ролики, поэтому выберет на марш-руте дорогу с наименьшим значением ti, а Татьяна предпочитает длинные ролики, поэтому выберет дорогу с наибольшим значением ti.
Вам будет интересно:
Заключительный этап всероссийской олимпиады школьников ВОШ по Физике 2020-2021 ответы и задания