Автор Всероссийская олимпиада школьников заключительный этап 2022 по информатике задания и ответы для 9, 10, 11 класса, олимпиада проходила с 24 по 30 марта 2022 года.
Задания олимпиады 1 тура для 9, 10, 11 класса
Задания олимпиады 2 тура для 9, 10, 11 класса
Ответы и решения для олимпиады
Опубликованы условия и ответы задач, которые выполняли участники заключительного этапа 2022 всероссийской олимпиады школьников по информатике. Также доступны предварительные результаты. Следить за результатами, которые показывают ребята, можно в реальном времени: группа А (9-10 классы) и группа В (11 класс).
Задания 1 тура олимпиады по информатике заключительного этапа 2022:
Задания 2 тура олимпиады по информатике заключительного этапа 2022:
Ответы заключительного этапа 2022 олимпиады по информатике:
1)Перед уроком физкультуры класс из n учеников построился в одну шеренгу. Все ученики в классе имеют разный рост. На i-м слева месте в шеренге стоит ученик с ростом pi (i = 1, 2, . . . , n, 1 ⩽ pi ⩽ n). Учитель физкультуры в начале урока может захотеть изменить порядок учеников в шеренге. Для этого он может ровно один раз выполнить следующую операцию: выбрать отрезок шеренги с l-й по r-ю позицию (1 ⩽ l ⩽ r ⩽ n), и отсортировать учеников на этом отрезке по возрастанию роста слева направо. Например, если n = 5 и изначально ученики стояли в порядке [5, 2, 4, 1, 3], а учитель выбрал l = 1 и r = 4, то после сортировки ученики будут стоять в порядке [1, 2, 4, 5, 3]. Используя эту операцию, учитель может постараться добиться того, чтобы два определенных ученика оказались как можно дальше друг от друга. Расстояние между учениками равно разности номеров позиций, на которых они стоят. Для каждой пары учеников учитель вычисляет максимальное расстояние, на котором они могут оказаться после выполнения одной операции сортировки отрезка. Помогите учителю найти сумму этих значений.
2)Сеть пунктов проката горнолыжного оборудования представляет собой корневое дерево, состоящее из n вершин, пронумерованных от 1 до n с корнем в вершине номер 1. В каждой вершине имеется пункт проката. Пункт, расположенный в i-й вершине, закупает оборудование по цене ci рублей за комплект. Пусть ai — суммарное количество комплектов горнолыжного оборудования, которое будет закуплено во всех пунктах проката, находящихся в поддереве вершины номер i. Согласно маркетинговым исследованиям для каждого i эта величина должна находиться в диапазоне: li ⩽ ai ⩽ ri . Необходимо определить, какое количество комплектов нужно закупить к началу сезона каждому из пунктов проката, чтобы для поддерева любой вершины сети общее количество комплектов находилось в указанном маркетологами диапазоне, а суммарная стоимость всех купленных комплектов была как можно меньше. Либо определить, что выполнить все условия маркетологов невозможно. Напомним, что граф называется деревом, если он связный и не содержит циклов. Между любыми двумя вершинами в дереве существует ровно один простой путь. Корневым деревом называется дерево, в котором есть одна выделенная вершина — корень. Поддеревом вершины v называют множество всех вершин, для которых вершина v лежит на пути от соответствующей вершины до корня. Обратите внимание, что сама вершина v тоже входит в это множество. Родителем вершины v называется такая вершина pv, что v и pv соединены ребром, и pv лежит на пути от v до корня.
3)Петя и его младший брат Коля пришли в аквапарк. Коля любит кататься с горки, которую можно схематически изобразить как часть треугольной сетки, вершины которой — узлы горки. В каждом узле можно выбрать, по какой трубе ехать дальше — влево-вниз или вправо-вниз. Уровни горки нумеруются сверху вниз, начиная с 0. На нулевом уровне у горки один узел — начало поездки, на первом уровне — два узла, . . . , на i-м уровне — i + 1 узлов. Всего у горки n + 1 уровней. Каждая поездка сверху вниз проходит ровно по n трубам. У каждого узла есть координаты: два числа (r, c) задают c-й слева узел на уровне r (0 ⩽ c ⩽ r ⩽ n). Обратите внимание, что и уровни, и узлы на каждом уровне нумеруются с 0. Если Коля находится в узле (r, c) и поедет влево-вниз, он попадет в узел (r + 1, c), а если он поедет вправо-вниз, он попадет в узел (r + 1, c + 1).
4)На координатной плоскости расположено прямоугольное поле с углами в точках (0, 0), (w, 0), (w, h) и (0, h). На поле расположены n прожекторов, i-й прожектор находится в точке с координатами (xi , yi). Каждый из прожекторов освещает угол в 90◦ , со сторонами параллельными осям координат, с вершиной в своей позиции.
Таким образом, есть четыре возможных направления угла, который может освещать прожектор: дано множество разрешенных направлений углов — одинаковое для всех прожекторов. Для каждого прожектора вы можете выбрать одно из разрешенных направлений. Требуется осветить прожекторами наибольшую возможную часть поля. Точка считается освещённой, если ее освещает хотя бы один прожектор. Вычислите максимальную возможную площадь части поля, которую можно осветить прожекторами, установив каждый из них в одном из разрешенных направлений.
5)Задан массив [p1, p2, . . . , pn], содержащий n различных целых чисел от 1 до n. Можно выбрать один любой отрезок массива с l-й по r-ю позицию включительно (1 ⩽ l ⩽ r ⩽ n), то есть [pl , pl+1, . . . , pr], и отсортировать элементы массива на этом отрезке в порядке возрастания. Например, если n = 5, изначально числа стояли в порядке [5, 2, 4, 1, 3], и был выбран отрезок с l = 2 и r = 4, то после сортировки числа в массиве будут стоять в порядке [5, 1, 2, 4, 3]. Расстояние между числами в массиве равно разности номеров позиций, на которых они стоят. Обозначим d(a, b) наибольшее возможное расстояние, на котором могут оказаться числа a и b после сортировки чисел на одном отрезке. Например, в приведенном выше массиве d(1, 3) = 4: чтобы числа 1 и 3 оказались на расстоянии 4, можно выбрать отрезок с l = 1 и r = 4. Тогда массив изменится следующим образом [5, 2, 4, 1, 3] → [1, 2, 4, 5, 3]. Выбранный отрезок подчеркнут. Требуется вычислить сумму значений d(a, b) по всем парам чисел a и b (1 ⩽ a < b ⩽ n). Например, если n = 5, то необходимо вычислить сумму d(1, 2) + d(1, 3) + d(1, 4) + d(1, 5) + d(2, 3) + d(2, 4) + + d(2, 5) + d(3, 4) + d(3, 5) + d(4, 5).
6)Сеть пунктов проката горнолыжного оборудования представляет собой корневое дерево, состоящее из n вершин, пронумерованных от 1 до n с корнем в вершине номер 1. В каждой вершине имеется пункт проката. Пункт, расположенный в i-й вершине, закупает оборудование по цене ci рублей за комплект. Пусть ai — суммарное количество комплектов горнолыжного оборудования, которое будет закуплено во всех пунктах проката, находящихся в поддереве вершины номер i. Согласно маркетинговым исследованиям для каждого i эта величина должна находиться в диапазоне: li ⩽ ai ⩽ ri . Необходимо определить, какое количество комплектов нужно закупить к началу сезона каждому из пунктов проката, чтобы для поддерева любой вершины сети общее количество комплектов находилось в указанном маркетологами диапазоне, а суммарная стоимость всех купленных комплектов была как можно меньше.
Либо определить, что выполнить все условия маркетологов невозможно. Напомним, что граф называется деревом, если он связный и не содержит циклов. Между любыми двумя вершинами в дереве существует ровно один простой путь. Корневым деревом называется дерево, в котором есть одна выделенная вершина — корень. Поддеревом вершины v называют множество всех вершин, для которых вершина v лежит на пути от соответствующей вершины до корня. Обратите внимание, что сама вершина v тоже входит в это множество. Родителем вершины v называется такая вершина pv, что v и pv соединены ребром, и pv лежит на пути от v до корня.