Автор Олимпиада по информатике 9, 10, 11 класс ответы и задания для заключительного этапа 2022-2023 учебный год всероссийской олимпиады школьников ВСОШ. Олимпиада прошла в Тюмени 1-7 апреля 2023 года.
→ Архив жюри, содержит задачи, тесты, решения
Решать задания олимпиады по информатике
zadanie-informatika-9-10-11klass-vos-2023Необходимо считывать данные из стандартного потока ввода. Выходные данные необходимо выводить в стандартный поток вывода. Баллы за подзадачу, если в условии не указано иное, начисляются только если все тесты этой подзадачи пройдены. Решение запускается на тестах для определенной подзадачи, если все тесты всех необходимых подзадач пройдены.
Для некоторых подзадач может также требоваться, чтобы были пройдены все тесты из условия. Для таких подзадач указана дополнительно буква У. Если вы решите перезагрузиться в другую операционную систему во время тура, для входа используйте логин «roi» и пароль «hi123».
Всероссийская олимпиада школьников по информатике 2023
Задача 1. Видеонаблюдение
Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт Безопасность в здании торгового центра обеспечивается с помощью системы видеонаблюдения. На компьютере у охранника открыта программа, которая выводит на экран видеопотоки с нескольких камер. Эта программа устроена следующим образом: на экране представлена прямоугольная сетка, состоящая из h строк и w столбцов.
Каждая из ячеек может быть пуста, либо туда выводится изображение с одной из камер. Для управления расположением изображений в программе, сотрудник службы безопасности может использовать кнопки «влево», «вправо», «вверх» и «вниз». Кнопка «влево» перемещает изображение из каждой ячейки в ячейку, находящуюся слева от нее. При этом, изображение из самой левой ячейки в каждом ряду перемещается в самую правую ячейку этого ряда. Аналогичным образом действуют кнопки «вправо», «вверх» и «вниз».
Кнопка «вправо» перемещает изображение из каждой ячейки в ячейку, находящуюся справа от нее. Изображения из самой правой ячейки в каждом ряду перемещаются в самую левую ячейку этого ряда. Кнопка «вверх» перемещает изображение из каждой ячейки в ячейку, находящуюся над ней. Изображения из самого верхнего ряда перемещаются в ячейки самого нижнего ряда. Кнопка «вниз» перемещает изображение из каждой ячейки в ячейку, находящуюся под ней. Изображения из самого нижнего ряда перемещаются в ячейки самого верхнего ряда.
Строки в сетке пронумерованы сверху вниз, столбцы пронумерованы слева направо. Ячейка на пересечении строки номер r и столбца номер c обозначается как (r, c). Ниже изображена сетка с 3 строками, 4 столбцами и тремя ячейками, содержащими изображения, с координатами (1, 1), (2, 4) и (3, 3). А также изображено, куда перейдут эти изображения при нажатии на каждую из четырёх кнопок.
Охраннику удобнее, чтобы ячейки на мониторе, которые содержат изображение с камер, были расположены как можно компактнее. Компактностью изображений назовём минимальную площадь подпрямоугольника сетки, который содержит все показываемые изображения. Заметим, что с помощью кнопок можно изменять компактность. Например, в левой части рисунка ниже показано расположение изображений, которое имеет компактность 12. Если один раз нажать на кнопку «вправо» и один раз нажать на кнопку «вверх», компактность изображений станет равна 4.
Вам дана сетка, которая содержит k ячеек с изображениями. Вычислите минимальную компактность, которую можно достичь, используя кнопки «влево», «вправо», «вверх» и «вниз», а также
минимальное необходимое для этого количество нажатий на кнопки.
Формат входных данных В первой строке даны три целых числа h, w и k — размеры сетки и количество ячеек с изображением (1 ⩽ h, w ⩽ 109 ; 1 ⩽ k ⩽ 100 000). В каждой из следующих k строк даны по два целых числа ri и ci — координаты ячейки, содержащей изображение (1 ⩽ ri ⩽ h; 1 ⩽ ci ⩽ w). Гарантируется, что все k ячеек различны.
Формат выходных данных Выведите два целых числа — минимальную компактность расположения изображений, которой можно достичь, используя кнопки, и минимально необходимое для достижения этой компактности количество нажатий на кнопки.
Задача 2. Тайное послание
Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт Это задача с двойным запуском. На каждом тесте ваше решение будет запущено два раза. На уроке информатики Алеся и Борис изучают криптографию. Ребята решили изобрести свой способ шифрования сообщений. Алеся выбирает k различных целых чисел от 1 до n и обозначает получившееся множество как T. Алеся хочет передать Борису в качестве сообщения множество T в зашифрованном виде. Для этого по множеству T Алеся построит и передаст Борису другое множество R, также состоящее из целых чисел от 1 до n.
Ребята не хотят, чтобы после шифрования размер сообщения изменялся, поэтому R также должно содержать ровно k чисел. А ещё они считают, что если T и R будут содержать хотя бы один общий элемент, то их шифрование будет недостаточно надежным. Поэтому не должно существовать числа, которое входит и в T, и в R, то есть множества T и R не должны пересекаться. Гарантируется, что k ⩽ n/2, поэтому по множеству T всегда возможно построить хотя бы одно множество R. Когда Борис получит зашифрованное сообщение R, он должен будет его расшифровать и получить исходное сообщение T. Помогите Алесе и Борису придумать и реализовать алгоритмы шифрования и дешифрования. При первом запуске ваша программа будет выступать в роли Алеси, а при втором запуске — в роли Бориса.
Формат входных данных В первой строке входных данных дано одно число a, равное 1 или 2 — номер запуска вашей программы. Во второй строке дано одно число m — количество сообщений (1 ⩽ m ⩽ 300 000), которое ваша программа должна зашифровать (в первом запуске) или расшифровать (во втором запуске). Следующие 2m строк содержат описания m сообщений, по две строки на сообщение. В первой строке сообщения записаны два целых числа ni и ki (2 ⩽ ni ⩽ 109 , 1 ⩽ ki ⩽ 300 000, ki ⩽ ni 2 ). Во второй строке сообщения записаны ki различных целых чисел от 1 до ni в возрастающем порядке. Гарантируется, что сумма всех значений ki в одном тесте не превосходит 300 000. Если a = 1, то данные числа являются исходным сообщением. Если a = 2, то данные числа являются результатом запуска вашей программы для шифрования какого-либо сообщения при первом запуске вашей программы.
Формат выходных данных Программа должна вывести m строк, i-я строка должна содержать ki различных целых чисел от 1 до ni в возрастающем порядке. При первом запуске для каждого исходного сообщения Ti программа должна вывести множество Ri , которое не должно пересекаться с Ti . При втором запуске программа для каждого зашифрованного сообщения Ri должна восстановить исходное сообщение Ti . Пример Обратите внимание, что в примере приведены конкретные варианты вывода в первом запуске и ввода во втором запуске.
Если ваша программа выведет другое множество R, при втором запуске ввод также будет другой. Также при втором запуске зашифрованные сообщения передаются программе участника не обязательно в том порядке, в котором они следовали при первом запуске.
Задача 3. Рекорды и антирекорды
Ограничение по времени: 3 секунды Ограничение по памяти: 512 мегабайт Перестановкой размера n называется последовательность n целых чисел a1, a2, . . . , an, в которой все значения от 1 до n встречаются ровно по одному разу. Последовательность b1, b2, . . . , bl является подпоследовательностью последовательности a1, a2, . . . , an, если b можно получить из a удалением некоторых элементов (то есть l ⩽ n и существуют i1 < i2 < . . . < il такие что ait = bt).
• Элемент последовательности ai называется рекордом, если он строго больше всех предыдущих элементов (то есть aj < ai для всех 1 ⩽ j < i).
• Элемент последовательности ai называется антирекордом, если он строго меньше всех предыдущих элементов (то есть aj > ai для всех 1 ⩽ j < i). Дана перестановка p1, p2, . . . , pn размера n. Требуется разделить её на две непустые подпоследовательности q и r. Иными словами, каждый элемент p должен попасть ровно в одну из подпоследовательностей. При этом требуется максимизировать сумму количества рекордов в q и количества антирекордов в r. Формат входных данных Каждый тест состоит из нескольких наборов входных данных. В первой строке содержится единственное целое число t (1 ⩽ t ⩽ 100 000) — количество наборов входных данных.
В следующих 2t строках следуют описания наборов входных данных. В первой строке описания каждого набора входных данных содержится одно целое число n — размер перестановки (2 ⩽ n ⩽ 200 000). Во второй строке описания каждого набора входных данных содержатся n целых чисел p1, p2, . . . , pn — исходная перестановка. Гарантируется, что среди элементов p каждое число от 1 до n встречается ровно по одному разу. Сумма n по всем наборам входных данных не превосходит 200 000.
Формат выходных данных Для каждого набора входных данных выведите одно целое число — максимальную возможную сумму количества рекордов в q и антирекордов в r в оптимальном разбиении. Система оценки Обозначим как N сумму значений n во всех наборах входных данных одного теста.
Задача 4. Ультра mex
Ограничение по времени: 3 секунды Ограничение по памяти: 512 мегабайт Рассмотрим A — множество неотрицательных целых чисел. Минимальное неотрицательное целое число, которое не встречается в A, обозначим как mex(A). Например, mex({0, 1, 2, 4, 5, 9}) = 3.
Эта функция часто используется, например, в теории игр. Операция «побитовое исключающее или» (обозначается «xor» в Паскале и Python, «^» в C++ и Java) для двух целых чисел определена следующим образом: i-й бит результата равен 1 тогда и только тогда, когда в одном из чисел этот бит 1, а в другом 0. Будем обозначать эту операцию символом ⊕. Например, 6 ⊕ 10 = 1102 ⊕ 10102 = 11002 = 12. Определим ещё одну операцию над множеством A, содержащим число 0. Операция будет называться «ультра».
Пусть m = mex(A). Заметим, что m > 0. Построим новое множество ultra(A) следующим образом: применим «побитовое исключающее или» с числом (m−1) ко всем элементам A. Например, ultra({0, 1, 2, 4, 5, 9}) = {0⊕2, 1⊕2, 2⊕2, 4⊕2, 5⊕2, 9⊕2} = {2, 3, 0, 6, 7, 11} = {0, 2, 3, 6, 7, 11}. Можно показать, что если множество A содержит 0, то множество ultra(A) также содержит 0. Выберем множество A0, состоящее из целых чисел от 0 до 2 k − 1 и содержащее 0. Рассмотрим следующую последовательность: • m0 = mex(A0), A1 = ultra(A0) • m1 = mex(A1), A2 = ultra(A1) • . . . • mi = mex(Ai), Ai+1 = ultra(Ai) • . . . Будем называть множество A0 mex-стабильным, если начиная с некоторого индекса l числа mi перестают меняться. То есть, для всех i ⩾ l выполнено mi = ml . Число ml будем называть mex-пределом множества A0. Вам даны числа k, n и p.
Вычислите количество множеств A0, которые: • Состоят из n различных чисел от 0 до 2 k − 1 (0 обязательно должен входить в A0); • Являются mex-стабильными; • mex-предел A0 равен p. Так как ответ может быть большим, выведите его по простому модулю M. Гарантируется, что (M − 1) делится на 2 18 . Формат входных данных В первой строке дано одно целое число M — модуль, по которому нужно посчитать ответ (3 ⩽ M ⩽ 109 ; (M − 1) делится на 2 18). Гарантируется, что M простое число. Во второй строке дано одно целое число t — количество наборов входных данных (1 ⩽ t ⩽ 100 000).
Для каждого набора входных данных в единственной строке даны три целых числа k, n и p (1 ⩽ k ⩽ 17; 1 ⩽ n, p ⩽ 2 k ). Формат выходных данных Для каждого набора входных данных на новой строке выведите одно целое число — количество искомых множеств A, взятое по модулю M.
Задача 5. Улитка на склоне
Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт Тихо взобравшись на вершину горы Фудзи, улитка хочет спуститься вниз. На склоне горы находится система тропинок, образующая подвешенное двоичное дерево.
Дерево содержит n вершин, соединенных n − 1 тропинками. На вершине горы находится корень дерева. В некоторых вершинах тропинка заканчивается, они являются листами дерева. От каждой вершины, кроме листьев, вниз по склону отходят ровно две тропинки, одна ведет налево, а другая — направо. Улитка хочет, начав в корне, спуститься по дереву и добраться до одного из листьев. Она будет спускаться, перемещаясь вниз по тропинкам.
В каждой вершине по пути улитка может выбрать одно из двух направлений дальнейшего спуска: налево или направо. Улитка может начать спуск в корне в любом из двух направлений. В каждой из последующих вершин улитка делает поворот, если она выбрала направление, отличающееся от выбранного в предыдущей вершине. Улитке неудобно поворачивать, поэтому на всем пути от корня до листа улитка готова сделать не более k поворотов. Пронумеруем вершины дерева от 1 до n, при этом корень получит номер 1. Вам дано q запросов. Каждый запрос описывается одной вершиной ui . Требуется найти количество листьев, в которых улитка сможет завершить свой спуск, если она будет спускаться из корня, сделает не более k поворотов, и по пути пройдет через вершину ui .
Формат входных данных В первой строке даны три целых числа n, k и q — количество вершин в дереве, максимальное количество поворотов, которое улитка готова сделать, и количество запросов (3 ⩽ n ⩽ 200 000; 0 ⩽ k ⩽ n; 1 ⩽ q ⩽ 200 000). В следующих n строках дано описание дерева. Первым в i-й строке дано целое число ti — количество тропинок, выходящих из i-й вершины (ti = 0 или ti = 2). Если ti = 2, то далее в той же строке даны два целых числа li и ri — номера вершин, в которые ведёт соответственно левая и правая тропинка из вершины i (1 ⩽ li , ri ⩽ n). Гарантируется, что это описание соответствует подвешенному двоичному дереву с корнем в вершине 1.
В следующих q строках даны запросы. В i-й строке дано одно целое число ui — номер вершины, через которую должна пройти улитка на своем пути (1 ⩽ ui ⩽ n). Формат выходных данных Для каждого запроса, выведите ответ на него в новой строке — количество листьев, в которых улитка может завершить свой маршрут, если она начинает в корне, спускается вниз, на своем пути совершает не больше k поворотов и проходит через вершину ui .
Задача 6. Конференция
Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт Тюменская Ассоциация Научных и Образовательных Сообществ организует конференцию, в рамках которой планировалось провести n мероприятий, пронумерованных от 1 до n. При этом i-е мероприятие задаётся двумя целыми числами li и ri — временем начала и окончания мероприятия.
Поскольку некоторые мероприятия могут перекрываться или даже полностью совпадать по времени, один человек не всегда может посетить все мероприятия конференции. Будем считать, что мероприятия i и j не пересекаются, если ri < lj или rj < li . Будем называть множество мероприятий совместным, если любые два различных мероприятия в этом множестве не пересекаются. Пусть максимальный размер совместного множества мероприятий на конференции равен m. Будем называть насыщенностью конференции отношение n/m.
В связи с сокращением финансирования, организаторы конференции приняли решение, что число мероприятий на конференции будет уменьшено ровно в два раза. При этом они хотят сохранить насыщенность конференции неизменной, поэтому максимальный размер совместного множества мероприятий в рамках конференции также должен уменьшиться ровно в два раза. Удачным образом оказалось, что в исходном плане конференции как количество мероприятий n, так и максимальное возможное количество мероприятий в совместном множестве m — чётные числа. Помогите организаторам выбрать множество из n/2 исходно запланированных мероприятий, которые необходимо провести, чтобы при этом размер максимального совместного множества выбранных мероприятий оказался равен m/2.
Формат входных данных Один тест содержит несколько наборов входных данных. В первой строке дано одно целое число t — количество наборов входных данных (1 ⩽ t ⩽ 50 000). В первой строке каждого описания набора дано одно целое число n — количество мероприятий в исходном плане (2 ⩽ n ⩽ 100 000, n — чётное). В следующих n строках каждого описания набора дано описание мероприятий. В i-й строке даны два целых числа li и ri — время начала и конца i-го мероприятия (1 ⩽ li < ri ⩽ 109 ).
Гарантируется, что m — размер максимального совместного множества мероприятий для исходного плана, чётно. Формат выходных данных Для каждого набора входных данных выведите в новой строке n/2 различных номеров мероприятий, которые необходимо провести. Если существует несколько подходящих ответов, вы можете вывести любой из них. Для проведенных мероприятий размер максимального совместного множества мероприятий должен быть равен m/2.
Задача 7. Яблоки по корзинам
Ограничение по времени: 2 секунды Ограничение по памяти: 512 мегабайт У Саши есть n яблок с целыми весами w1, w2, . . . , wn, которые лежат на столе, а также две вместительные корзины. Саша выбирает целое число k и рассматривает яблоки с весом не больше k. После этого она может положить каждое яблоко с весом wi ⩽ k в одну из двух корзин, либо оставить его на столе. Яблоки с весом wi > k в любом случае остаются на столе.
Назовем пару чисел (x, y) k-достижимой, если Саша может положить некоторые яблоки с весом не больше k в корзины так, чтобы сумма весов яблок в первой корзине оказалась равна x, а сумма весов яблок во второй корзине оказалась равна y. Назовем пару чисел (a, b) k-идеальной, если для всех x и y, где 0 ⩽ x ⩽ a и 0 ⩽ y ⩽ b, пара (x, y) является k-достижимой. Саша рассматривает q троек чисел k, a, b и для каждой из них хочет понять, является ли k-идеальной пара (a, b). Формат входных данных В первой строке даны два целых числа n и q — количество яблок, которые есть у Саши, и количество запросов, которые вам надо обработать (1 ⩽ n, q ⩽ 300 000). Во второй строке даны n целых чисел w1, w2, . . . , wn — веса яблок, которые есть у Саши (1 ⩽ wi ⩽ 1012).
В третьей строке находится целое число z, которое используется для формирования запросов, на которые необходимо ответить (0 ⩽ z ⩽ 106 ). В следующих q строках даны описания запросов. Запросы пронумерованы от 1 до q. Каждая строка содержит три целых числа j, c и d (0 ⩽ j, c, d ⩽ 1018). Запрос формируется из чисел в этой строке по следующим правилам. Вычислим v, как сумму номеров запросов, сделанных до текущего, для которых заданная в запросе пара (a, b) оказалась k-идеальной. Тогда в текущем запросе k = j − v · z; a = c − v · z; b = d − v · z.
Гарантируется, что k, a, b ⩾ 0. Обратите внимание, что при z = 0 (что верно для большинства подзадач), значения k, a и b равны j, c и d соответственно. То есть параметры запроса не зависят от ответов на предыдущие запросы и даны во входных данных в явном виде. Формат выходных данных На каждый запрос выведите «Yes», если пара (a, b) в данном запросе является k-идеальной, иначе выведите «No».
Задача 8. Выполнить план, но не перевыполнить
Ограничение по времени: 3 секунды Ограничение по памяти: 512 мегабайт Это интерактивная задача. Требуется разработать планы производства автомобилей и запасных частей в некоторой стране. Всего в стране n городов, в которых расположены заводы, задействованные в производстве. В i-м городе на заводе могут работать от li до ri человек включительно. Некоторые города соединены двусторонними дорогами, при этом дорожная сеть имеет форму дерева: от каждого города можно единственным способом добраться до любого другого города, не проезжая через один город дважды.
Планом производства будем называть последовательность целых чисел [a1, a2, . . . , an], где ai — количество человек, которые будут работать на i-м заводе (li ⩽ ai ⩽ ri). После формирования плана производства некоторые заводы будут выбраны как сборочные, они будут производить автомобили, а остальные будут производить запчасти. Выбор считается рациональным, если никакие два сборочных завода не соединены дорогой напрямую. Среди всех возможных рациональных выборов будет выбран тот, для которого суммарное количество работников сборочных заводов будет максимально. Это число называется эффективностью плана [a1, a2, . . . , an]. В этой задаче для некоторых значений v1, v2, . . . , vq вам необходимо выяснить, существует ли план с эффективностью vi . Если такой план существует, вам может потребоваться предъявить такой план. Зафиксированы целочисленные параметры x, y и m.
Рассмотрим план [a1, a2, . . . , an]. Сертификатом этого плана назовем число k = ⊕n j=1 ( (x · j + y · a 2 j ) mod m ) , где ⊕ — это операция «побитового исключающего или». Напомним, что эта операция обозначается «xor» в Паскале, «^» в C++, Python и Java; для двух целых чисел она определена следующим образом: i-й бит результата равен 1 тогда и только тогда, когда в одном из чисел этот бит 1, а в другом 0. Например, 6 ⊕ 10 = 1102 ⊕ 10102 = 11002 = 12. Процесс составления планов будет состоять из двух этапов. На первом этапе вам будут даны значения v1, v2, . . . , vq. Для каждого из них вам необходимо выяснить, существует ли план с эффективностью vi и, если его не существует, вывести для этого запроса −1, а если существует, то неотрицательное целое число ki . На втором этапе некоторые планы будут проверены: c раз вам будет дано целое число i (1 ⩽ i ⩽ q).
В ответ на такой запрос требуется либо вывести −1, если плана с эффективностью vi не существует, либо предоставить план [a1, a2, . . . , an], сертификат которого равен ki , а эффективность равна vi . Предоставление сертификатов составленных планов и последующая проверка будут реализованы в интерактивном режиме. До того, как вы предоставите сертификаты, вы не будете знать, какие планы будут проверены. Поэтому в тех подзадачах, в которых c > 0, необходимо еще на первом этапе подготовиться к проверке, выведя для значений эффективности vi , где искомый план существует, такие значения ki , для которых вы сможете на втором этапе предъявить план с сертификатом, равным ki .
Региональный этап 2023 по информатике 9, 10, 11 класс задания и ответы
Региональный этап 2023 по информатике 9, 10, 11 класс задания и ответы олимпиады