Региональный этап 2024-2025 всероссийской олимпиады школьников по информатике задания, ответы и решения для 9, 10, 11 класса. Данная олимпиада прошла у школьников 18, 20 января 2025 года. Предварительные результаты ВСОШ будут известны позднее. Критерии и решение опубликованы после заданий.
Итоги регионального этапа подводятся отдельно по классам, победители и призеры регионального этапа определяются отдельно в каждом классе. Региональный этап всероссийской олимпиады школьников по информатике проводится в два компьютерных тура. Длительность каждого тура составляет пять астрономических часов. Все участники регионального этапа должны быть допущены к участию в обоих турах, за исключением лиц, удаленных за нарушение Порядка проведения.
Задания олимпиады по информатике региональный этап 2025
zadanie-inf-1-2-tur-region-2025Разбор заданий регионального этапа 2025
VsOSh2025_informatika_razbor_zadaniyРешение для 9-11 класса
otveti-inf-region-2025-9-10-11Задача 1. Кузнечик 2D
Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт В левом-нижнем углу квадратной клетчатой доски размером n × m стоит k-кузнечик. За один ход k-кузнечик перемещается по доске вправо, вверх или вправо-вверх по диагонали не более чем на k клеток.
Необходимо передвинуть k-кузнечика в правый верхний угол доски в клетку (n, m). Выведите, за какое минимальное число ходов можно передвинуть k-кузнечика из клетки (1, 1) в клетку (n, m). Формат входных данных В первой строке заданы три целых числа n, m и k — размеры сторон доски и максимальное число клеток, на которое может ходить k-кузнечик, соответственно (1 6 n, m, k 6 109 ). Формат выходных данных Выведите одно число — минимальное число ходов, необходимое, чтобы передвинуть k-кузнечика из клетки (1, 1) в клетку (n, m). Система оценки Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Задача 2. Простоватые числа
Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт Скажем, что число является простоватым, если произведение цифр этого числа в десятичной системе счисления является простым числом. Например, простоватым является число 51, а число 47 не является. Требуется посчитать количество простоватых чисел от l до r. Напомним, что целое число p > 1 называется простым, если оно имеет ровно два делителя: 1 и p. Формат входных данных Первая строка содержит одно целое число l (1 6 l 6 10100 000). Вторая строка содержит одно целое число r (l 6 r 6 10100 000). Обратите внимание, что числа во вводе не помещаются в стандартные типы данных для целых чисел в большинстве языков программирования, в частности, в C++. Необходимо каким-либо специальным образом считывать входные данные, например, в виде строки. Формат выходных данных Выведите количество простоватых чисел от l до r. Система оценки Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Задача 3. Кислотные дожди
Для сборки исследовательской лаборатории на Венеру доставлены n блоков. Блоки расположены в ряд, i-й блок имеет высоту hi . Сборку будет осуществлять специальный робот. В процессе сборки последовательные сегменты блоков будут постепенно объединяться. При этом порядок блоков в ряду не будет меняться. Исходно каждый блок представляет собой отдельный сегмент, сегменты пронумерованы от 1 до n в том же порядке, что и блоки. Если есть два соседних сегмента, составленных из блоков: сегмент из блоков A = [i, i+ 1, . . . , i+p−1] и сегмент из блоков B = [i+p, i+p+ 1, . . . , i+p+q −1], то после их объединения в один получается сегмент AB = [i, i+ 1, . . . , i+p−1, i+p, i+p+ 1, . . . , i+p+q −1].
Инструкция по сборке состоит из n−1 инструкций. Каждая инструкция характеризуется одним числом, j-я инструкция характеризуется числом kj . После выполнения этой инструкции сегменты с номерами kj и kj + 1 объединяются в один, получившийся сегмент занимает место в последовательности сегментов на месте двух объединенных сегментов, и вводится новая нумерация на сегментах в том порядке, в котором они расположены — номера сегментов, начиная с kj + 2, уменьшаются на один. После выполнения всех инструкций все сегменты окажутся объединены в один общий сегмент. На Венере постоянно идут кислотные дожди, поэтому в процессе сборки важно для каждого сегмента блоков понимать, сколько жидкости может скопиться в этом сегменте. Пусть сегмент состоит из блоков высотой hl , hl+1, . . . , hr. Для p, где l 6 p 6 r определим глубину блока c высотой hp в этом сегменте следующим образом.
Посчитаем величины lp = max{hl , . . . , hp}, rp = max{hp, . . . , hr}. Это самые высокие блоки в сегменте слева и справа от p-го. Тогда глубина блока p в его сегменте равна dp = min(lp, rp)−hp, заметим, что dp > 0. Емкостью сегмента будем называть сумму глубин блоков этого сегмента, то есть w = dl + dl+1 + . . . + dr. Задана последовательность объединений сегментов. Выведите после каждого объединения емкость получившегося сегмента. Рисунок на следующей странице показывает процесс выполнения инструкции из примера, над каждым блоком указана его глубина, а для нового сегмента показана его емкость.
Формат входных данных Первая строка содержит одно целое число n — количество блоков (2 6 n 6 105 ). Во второй строке записано n чисел h1, . . . , hn (1 6 hi 6 109 ). В третьей строке записаны n − 1 чисел — инструкции по объединению сегментов. Каждая инструкция характеризуется одним числом kj (1 6 kj 6 n − j). Формат выходных данных Вывод должен содержать n−1 чисел — после каждого объединения сегментов выведите емкость получившегося объединенного сегмента.
Задача 4. Поиск сокровищ
Для поиска полезных ископаемых ученые разработали гравитационный сканер. Представим область для поисков как таблицу из k строк и n столбцов. Нумерация строк идет от 1 до k сверху вниз, нумерация столбцов от 1 до n слева направо. В каждой клетке таблицы могут находиться полезные ископаемые. Сканер работает следующим образом: он может быть запущен в столбце p и возвращает количество клеток в зоне сканирования, которые содержат полезные ископаемые. Зона сканирования включает все клетки столбца p, верхние k − 1 клетку столбца p − 1, верхние k − 2 клетки столбца p−2, и так далее. На рисунке показана зона сканирования для поля с k = 3, n = 5 и всех значений p. Вам даны значения, которые вернул сканер для всех p, обозначим за bp значение в столбце p.
Будем называть таблицу, где для каждой клетки определено, находятся ли в ней полезные ископаемые, корректной, если для нее сканер возвращает верные значения. Например, если в примере выше сканер вернул значения [2, 1, 2, 3, 2], то одна из корректных таблиц может выглядеть следующим образом (клетки, содержащие ископаемые, обозначены черным треугольником): по заданным значениям, которые вернул сканер, вычислите количество корректных таблиц и выведите остаток от деления этого количества на число 109 + 7. Обратите внимание, что, возможно, сканер неисправен, и корректных таблиц вообще нет, тогда ответ равен 0.
Задача 5. Разность квадратов
На доске были выписаны два квадрата натуральных чисел: x 2 и y 2 , где l 6 y 2 < x2 6 r. Числа x 2 и y 2 стерли и выписали на доске их разность d. По заданным l, r и d вычислите, сколько различных пар натуральных чисел x 2 , y2 могло быть выписано на доске. Формат входных данных В первой строке даны три числа d, l и r (1 6 d 6 109 , 1 6 l 6 r 6 1018). Формат выходных данных Вывод должен содержать количество подходящих пар квадратов. Система оценки Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. В первом примере подходят числа 100 и 36. Во втором примере также подходят числа 256 и 196.
Задача 6. Перекошенное разбиение
Дан массив [a1, a2, . . . , an], состоящий из неотрицательных целых чисел. Рассмотрим разбиение массива на k непустых отрезков подряд идущих элементов. Назовем перекосом разбиения разность между максимальной и минимальной суммой чисел в отрезках разбиения. Необходимо найти максимальный перекос разбиения данного массива на k подотрезков. Например, если массив равен [2, 1, 3, 4], то у разбиения [2, 1, 3][4] перекос равен 6 − 4 = 2, у разбиения [2, 1][3, 4] перекос равен 7 − 3 = 4, а у разбиения [2][1, 3, 4] перекос равен 8 − 2 = 6. Последний вариант является оптимальным среди всех разбиений массива на два непустых отрезка. Формат входных данных Первая строка содержит два целых числа n и k (2 6 k 6 n 6 300 000) — длину массива и количество подотрезков, соответственно. Вторая строка содержит n целых чисел ai (0 6 ai 6 109 ) — элементы массива. Формат выходных данных Следует вывести одно число — максимальный перекос разбиения данного массива на k отрезков. Система оценки Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Первый пример разобран в условии задачи. Во втором примере оптимальным разбиением является [2][1][3, 4][1]. Максимальная сумма на подотрезках в данном разбиении равна 3 + 4 = 7, минимальная сумма равна 1, таким образом, перекос равен 6.
Задача 7. Главное правило личных олимпиад
Надеемся, вы помните главное правило написания личных олимпиад: по каждой задаче нужно набрать баллы! Нельзя уйти с контеста с нулем по задаче. Промоделируем тур олимпиады. Пусть на туре предложено n задач, i-я задача состоит из ki подзадач, j-я подзадача i-й задачи приносит ci,j баллов. Зависимостей между подзадачами нет, поэтому можно в каждой задаче выбрать любое множество подзадач и его решить. При этом нельзя выбрать пустое множество, ведь тогда по задаче будет 0 баллов, а это противоречит главному правилу написания личных олимпиад. Необходимо выяснить, можно ли, придерживаясь главного правила личных олимпиад, набрать на туре ровно s баллов. Формат входных данных Первая строка содержит два целых числа n, s (1 6 n 6 100 000, 1 6 s 6 100 000) — количество задач в контесте и необходимую сумму баллов, соответственно. Далее следуют описания задач. Описание каждой задачи состоит из двух строк.
Первая строка описания i-й задачи содержит одно целое число ki (1 6 ki 6 100 000) — количество подзадач в i-й задаче. Вторая строка описания i-й задачи содержит ki целых чисел ci,1, ci,2, . . . , ci,ki (1 6 ci,j 6 100 000) — баллы за подзадачи. Гарантируется, что сумма k1 + k2 + . . . + kn по всем задачам не превосходит 100 000. Гарантируется, что произведение (k1 + k2 + . . . + kn) · s не превосходит 107 . Формат выходных данных Если решения не существует, выведите «No». В противном случае в первой строке выведите «Yes». Далее необходимо вывести описание решенных подзадач для каждой задачи. Описание i-й задачи начинается с целого числа mi (1 6 mi 6 ki) — количества решенных подзадач i-й задачи. Далее следуют mi различных целых чисел pi,1, pi,2, . . . , pi,mi (1 6 pi,j 6 ki) — номера решенных подзадач в i-й задаче. Если можно найти несколько подходящих способов набрать s баллов, выведите любой из них. Система оценки Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Задача 8. Туристический маршрут
Школьники приехали на экскурсию в новый город и решили осмотреть его достопримечательности. Представим город в виде прямоугольной сетки n × m, в некоторых клетках которой могут находиться достопримечательности. Герои начинают свой путь в клетке (1, 1), они хотят дойти до клетки (n, m), а затем вернуться обратно. В городе есть k достопримечательностей, они расположены в клетках (x1, y1), . . . ,(xk, yk), друзья обязательно хотят посетить их все. За одну минуту можно перейти из клетки (a, b) в клетку (c, d), если они являются соседними по стороне, то есть выполняется равенство |a−c|+|b−d| = 1. Легко видеть, что на маршрут необходимо потратить хотя бы 2n + 2m − 4 минут, будем рассматривать только такие маршруты.
Школьники считают маршрут интересным, если выполняются следующие условия: • для того, чтобы пройти маршрут, друзья потратят ровно 2n + 2m − 4 минут; • маршрут проходит через каждую клетку не более одного раза. • маршрут проходит через все клетки, которые содержат достопримечательности. Помогите школьникам понять, сколько существует различных интересных маршрутов. Так как это число может оказаться достаточно большим, то выведите его остаток при делении на 109 + 7. Формат входных данных В первой строке указаны числа n, m и k (3 6 n, m 6 106 , 0 6 k 6 2 000). В последующих k строках указано по паре чисел xi , yi (1 6 xi 6 n, 1 6 yi 6 m), гарантируется, что все пары (xi , yi) различны. То есть для любой пары индексов (i, j) (1 6 i < j 6 n) верно одно из двух: xi 6= xj или yi 6= yj . Формат выходных данных Следует вывести единственное число — остаток от деления числа интересных маршрутов на 109 + 7.
Смотрите задания регионального этапа прошлого года
Региональный этап 2024 по информатике 9, 10, 11 класс задания и ответы олимпиады ВСОШ