региональный этап 2024 олимпиада ВСОШ

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

Автор

Задания, ответы и решения регионального этапа 2023-2024 олимпиады по информатике для 9, 10 и 11 классов, всероссийская олимпиада школьников ВСОШ проходила 21-22 января 2024 года. Результаты будут опубликованы скоро на официальном сайте.

→ Скачать задания олимпиады

→ Скачать ответы и решения

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

Задания олимпиады по информатике 9, 10, 11 класс региональный этап 2024

informatika-region-2024-zadanie-olimp

Ответы и решения

otveti-informatika-region-2024-olimp

Задача 1. Посадка в самолет

Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт В самолетах авиакомпании Битавиа кресла расположены в n рядов, при этом в каждом ряду по шесть мест, между третьим и четвертым местом находится проход. Некоторые пассажиры регистрируются заранее онлайн, другие пассажиры регистрируются на стойке регистрации в аэропорту. При онлайн-регистрации пассажир может выбрать любое место и не может его затем менять.

Например, при n = 6 рассадка в самолете после онлайн-регистрации может выглядеть так (крестиками отмечены занятые места) На стойку регистрации придут m пассажиров. По правилам Битавиа нужно рассадить их в самолете таким образом, чтобы итоговая рассадка в самолете была симметрична относительно прохода. То есть, если в некотором ряду на первом кресле сидит пассажир, то в том же ряду на шестом кресле тоже должен сидеть пассажир. То же самое справедливо для второго и пятого, третьего и четвертого кресел, соответственно.

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

В первой строке содержатся два целых числа n и m — количество рядов в самолете и количество пассажиров, которые придут на стойку регистрации (1 6 n 6 1000, 0 6 m 6 6000). В следующих n строках задана изначальная рассадка в самолете после онлайн-регистрации.

В каждой строке содержится по шесть символов, при этом i-й символ j-й строки равен «X» (заглавная английская X), если i-е место в j-м ряду уже занято и «.» (точка) иначе. Если искомой рассадки не существует, выведите «Impossible». Иначе выведите n строк по шесть символов — итоговую рассадку в самолете. При этом i-й символ j-й строки должен быть равен «X», если место занято, и «.», если свободно. Если существует несколько решений, разрешается вывести любое.

Задача 2. Битоническая последовательность

Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт Последовательность [b1, b2, . . . , bk] называется битонической, если выполнены неравенства b1 < b2 < . . . < bi > . . . > bk для некоторого 1 6 i 6 k. Например, последовательности [1], [1, 2, 3, 2], [1, 4, 10], [3, 2] являются битоническими, а последовательности [1, 1], [2, 1, 3] — нет

Задана последовательность [a1, a2, . . . , an]. Требуется количество пар (l, r) таких, что 1 6 l 6 r 6 n и последовательность [al , al+1, . . . , ar] является битонической Формат входных данных Первая строка ввода содержит число n (1 6 n 6 300 000)

Вторая строка ввода содержит n целых чисел: a1, a2, . . . , an (1 6 ai 6 n). Формат выходных данных Выведите одно число — количество пар (l, r), таких, что 1 6 l 6 r 6 n и последовательность [al , al+1, . . . , ar] является битонической. Система оценки Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Задача 3. Игра с таблицей

Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт Дана таблица A из h строк и w столбцов, в каждой ячейке которой записано целое число. Строки пронумерованы от 1 до h сверху вниз, столбцы пронумерованы от 1 до w слева направо. Разрешается применять к этой таблице следующие операции: • выбрать столбец таблицы и удалить его (столбцы слева и справа от него становятся соседними); • выбрать строку таблицы и удалить ее (строки сверху и снизу от нее становятся соседними).

Эти операции разрешается применить произвольное число раз в любом порядке. Определите, возможно ли при помощи этих операций получить из исходной таблицу с суммой чисел, равной заданному числу s, и если да, то какие операции и в каком порядке необходимо применить. Формат входных данных Первая строка ввода содержит числа h и w — размеры таблицы (1 6 h, w 6 15). Каждая из следующих h строк содержит по w целых чисел — таблицу A (0 6 Ai,j 6 109 ) В последней строке ввода находится число s — необходимая сумма (1 6 s 6 1018)

Формат выходных данных Если получить таблицу с суммой чисел s из исходной невозможно, выведите строку «NO» Иначе: • В первой строке выведите строку «YES». • Во второй строке выведите единственное число k — количество операций с таблицей, которые необходимо применить, чтобы получить из неё таблицу с суммой чисел s. • В каждой из следующих k строк выведите по два целых числа tj , ij , где tj = 1, если очередная операция производится со строкой, и tj = 2, если она производится со столбцом таблицы. Число ij должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с которой эта операция производится.

Задача 4. Выбор столицы

Ограничение по времени: 2 секунды Ограничение по памяти: 512 мегабайт Дано неориентированное дерево — связный граф из n вершин без циклов, и число k. Зафиксируем некоторую вершину s дерева и назовем ее столицей. Ориентируем ребра дерева в направлении от столицы. Иными словами, ориентируем ребро (u, v) в направлении u → v, если при подвешивании дерева за вершину s вершина u является родителем вершины v.

Заметим, что при таком ориентировании ребер каждая вершина достижима из столицы Определим расстояние до вершины v графа как минимальное количество ребер на пути из s в v. Назовем доступностью вершины s максимальное из расстояний до всех вершин Разрешается добавить в дерево не более k дополнительных ориентированных ребер Для каждой вершины s дерева определите, какой минимальной доступности можно достичь, если выбрать вершину s в качестве столицы. Обратите внимание, что в некоторых подзадачах требуется вывести ответ только для первой вершины.

Формат входных данных Первая строка содержит три целых числа n, k и t (2 6 n 6 2 · 105 , 1 6 k 6 n − 1, n · k 6 2 · 105 , 0 6 t 6 1) — количество вершин дерева, ограничение на максимальное количество добавленных ребер и число t, равное 0, если нужно вывести ответ только для вершины с номером 1, и равное 1 иначе. Каждая из следующих n − 1 строк содержит два целых числа ui , vi (1 6 ui , vi 6 n) — ребра дерева. Гарантируется, что заданные ребра образуют дерево. Формат выходных данных В случае, если t = 0, выведите единственное целое число: минимальную доступность, которую можно достичь, выбрав вершину с номером 1 в качестве столицы, и добавив не более k дополнительных ориентированных ребер.

В случае, если t = 1, выведите n чисел: i-е число равняется минимальной доступности, которую можно достичь, выбрав вершину i в качестве столицы, и добавив не более k дополнительных ориентированных ребер. Система оценки Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Задача 5. Разбиение массива

Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт Дан массив A = [a1, a2, . . . , an], содержащий n натуральных чисел. Требуется раскрасить элементы массива в два цвета таким образом, чтобы не существовало двух элементов x и y одного цвета, таких, что x нацело делился на y и выполнялось равенство x y = p, где p — простое число.

Гарантируется, что такая раскраска существует Напомним, что целое число p > 1 называется простым, если оно имеет ровно два делителя: 1 и p Формат входных данных Первая строка содержит одно целое число n (1 6 n 6 100 000) — количество элементов в массиве. Вторая строка содержит n целых чисел a1, a2, . . . , an (1 6 ai 6 106 ) — элементы массива.

Формат выходных данных Выведите описание разбиения массива на два множества в следующем формате Выведите n целых чисел, i-е из которых равняется 1, если элемент ai надо раскрасить в первый цвет, и 2, если элемент ai надо раскрасить во второй цвет. Если существует несколько подходящих раскрасок, вы можете вывести любую из них. Система оценки Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Задача 6. Бактерии

Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт В биологической лаборатории проводят эксперимент. В начале у ученых есть n замороженных бактерий, пронумерованных от 1 до n. Согласно плану эксперимента замороженная бактерия с номером i попадёт в чашку Петри через ai секунд после начала эксперимента.

Если таких бактерий несколько, они все попадают туда одновременно Как только замороженная бактерия оказывается в чашке Петри, она размораживается и начинает созревать. Созревание бактерии с номером i занимает ti секунд. Как только бактерия созрела, она начинает размножаться: немедлено превращается в две созревшие бактерии, и затем каждая созревшая бактерия в конце каждой секунды снова делится на две созревшие бактерии Размером колонии называется общее количество бактерий в чашке Петри. Цель эксперимента — определить, через сколько секунд размер колонии будет в точности равен m Помогите ученым определить искомое число секунд или выясните, что размер колонии никогда не будет в точности равен m.

Формат входных данных В первой строке даны целые числа n, m (1 6 n 6 2·105 , 1 6 m 6 109 ) — количество замороженных бактерий и желаемый размер колонии. Во второй строке даны n целых чисел a1, a2, . . . , an (1 6 ai 6 109 ) — времена перемещения замороженных бактерий в чашку Петри. В третьей строке даны n целых чисел t1,t2, . . . ,tn (1 6 ti 6 109 ) — продолжительность созревания замороженных бактерий. Формат выходных данных Если размер колонии никогда не будет равен m, выведите −1. В противном случае выведите число секунд после начала эксперимента, через которое размер колонии будет в точности равен m. Система оценки Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Задача 7. Разбиение на тройки

Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт На день рождения Маше как обычно подарили массив a из n натуральных чисел, в котором каждое число находится в пределах от 1 до m включительно. Маша очень любит число три, поэтому длина массива делится на три. Маша решила объединять числа в тройки: каждая тройка чисел должна состоять или из трех одинаковых чисел, или из трех последовательных чисел.

Другими словами, каждая тройка имеет или вид (x, x, x), или (x, x + 1, x + 2), где x — какое-то натуральное число Маша хочет поиграть с подаренным массивом, и ее интересует количество способов разбить числа этого массива на такие тройки. Два способа разбиения считаются различными, если нельзя установить взаимно-однозначное соответствие между тройками первого разбиения и тройками второго разбиения, что числа внутри соответствующих троек равны.

Так как количество разбиений может быть большим, Маше достаточно знать его остаток по модулю 109 + 7 Помогите Маше посчитать количество способов разбить числа подаренного ей массива на тройки по модулю 109 + 7 Формат входных данных Первая строка входных данных содержит два целых числа n и m (1 6 n 6 5000, 1 6 m 6 5000, n = 3 · k для какого-то натурального k). Вторая строка содержит n целых чисел ai — числа массива (1 6 ai 6 m). Формат выходных данных В единственной строке одно число — количество способов разбить числа массива на тройки по модулю 109 + 7. Система оценки Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены/

Задача 8. Обходы бинарного дерева

Ограничение по времени: 2 секунды Ограничение по памяти: 512 мегабайт Бинарное дерево — это набор вершин, у каждой из которых может быть левый и правый ребёнок. Одна из вершин является корнем дерева, она не является ребёнком какой-то другой. Начав в корне и каждый раз переходя в одного из детей, можно дойти до любой вершины. Множество вершин, до которых можно дойти из заданной, называется её поддеревом. У бинарного дерева есть три основных обхода: прямой (pre-order ), центрированный (in-order ) и обратный (post-order ). Прямой обход дерева — это порядок его вершин, полученный следующим рекурсивным алгоритмом: 1. Добавить корень дерева в обход.

2. Если у корня есть левый ребёнок, выписать прямой обход его поддерева. 3. Если у корня есть правый ребёнок, выписать прямой обход его поддерева. В центрированном обходе корень дерева выписывается между обходами поддеревьев его детей, в обратном — после обходов поддеревьев его детей. Обобщим эти три варианта обхода: пусть в каждой вершине записано целое число x от −1 до 1, обозначающее, в какой момент мы выписываем эту вершину, а именно: • x = −1: до обходов поддеревьев её детей; • x = 0: между обходами поддеревьев её детей; • x = 1: после обходов поддеревьев её детей. Таким образом, если во всех вершинах записано −1, обход является прямым, если 0 — центрированным, если 1 — обратным. Рассмотрим дерево с n вершинами, пронумерованных от 1 до n. Корень дерева — вершина 1. Изначально во всех вершинах записано число −1.

В рамках исследования необходимо обработать q запросов одного из следующих типов: 1. Поменять числа в вершинах l, l + 1, . . . , r на x (x равен −1, 0 или 1). 2. Сообщить, на какой позиции в текущем обходе будет стоять вершина i. Необходимо вывести ответы на все запросы второго типа. Формат входных данных В первой строке входных данных даны два целых числа n и q (1 6 n, q 6 100 000). В следующих n строках даны по два целых числа Li и Ri (0 6 Li , Ri 6 n) — номер левого и правого ребёнка вершины i соответственно, либо 0, если соответствующий ребёнок отсутствует Гарантируется, что Li и Ri задают корректное бинарное дерево В следующих q строках даны запросы. Первое число в строке t (t ∈ {1, 2}) — тип запроса В случае запроса первого типа далее даны целые числа l, r и x (1 6 l 6 r 6 n, x равен −1, 0 или 1) — границы отрезка вершин, в которых меняются числа, и новое значение. В случае запроса второго типа далее дано число i (1 6 i 6 n) — номер вершины, позицию которой в обходе необходимо вывести.

Требование и информация

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

2.9. Если жюри считает, что ответ на вопрос следует из условия задачи, оно отвечает «без комментариев» или «смотри условие». В противном случае жюри может дать разъяснение.

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

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

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

2.14. Для предотвращения утечки информации о содержании задач участники не вправе покидать место проведения олимпиады или пользоваться средствами связи до начала тура во всех субъектах Российской Федерации. Оргкомитет регионального этапа в случае необходимости должен предоставить таким участникам помещение для ожидания начала тура во всех субъектах РФ.

2.16. Для ознакомления с тестирующей системой перед основными турами организуется пробный тур.

2.17. Пробный тур проводится по задачам, которые предоставляются в комплекте олимпиадных заданий, подготовленном ЦПМК по информатике.

2.18. Пробный тур может проводиться в очной форме перед первым туром либо в дистанционной форме с использованием информационно-коммуникационных технологий.

2.19. Продолжительность пробного тура при очном проведении должна составлять не менее одного часа.

2.20. В случае проведения пробного тура в дистанционной форме он проводится заранее, не менее чем за один день до первого тура. Продолжительность пробного тура при дистанционном проведении должна составлять не менее двух суток.

Задания и ответы заключительного этапа 2023

Задания и ответы заключительного этапа 2023 ВСОШ всероссийской олимпиады школьников

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