Автор Задания, ответы, разбор заданий регионального этапа 2022-2023 олимпиады по информатике для 9, 10 и 11 классов, всероссийская олимпиада школьников ВСОШ проходила 21-23 января 2023 года. Результаты будут опубликованы скоро.
Задания олимпиады 1 тур
olimp_reg_23_1tЗадания 2 тура
2tur-infОтветы и решения
otveti_olimp_vos-2023Задача 1. Разделение прямоугольника. Алена играет в настольную игру «Огромное Поле». Рассмотрим прямоугольное клетчатое поле размером a × b. Необходимо разделить его на m прямоугольников вертикальными или горизонтальными разрезами. Прямоугольники не обязательно должны получиться равными. Необходимо суммарно провести ровно k разрезов. Каждый разрез представляет собой прямую линию от одного края поля до другого края поля. Разрезы разрешено делать только по границам клеток — линиям сетки. Выведите, сколько провести горизонтальных (0 6 h < a) и сколько вертикальных (0 6 v < b) разрезов. Если поле можно разрезать несколькими способами, выведите тот, в котором горизонтальных разрезов меньше. Если поле нельзя разрезать требуемым образом, выведите −1.
Задача 2. Произведение Фибоначчи. Напомним, что последовательность чисел Фибоначчи определяется следующим образом: F0 = 1, F1 = 1, Fn = Fn−2 + Fn−1. Последовательность чисел Фибоначчи начинается так: 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .. Дано натуральное число n. Требуется посчитать количество способов представить его как произведение чисел Фибоначчи, каждое из которых больше 1. Формат входных данных Первая строка ввода содержит целое число t — количество тестов (1 6 t 6 50) Следующие t строк содержат тесты, каждая строка содержит одно целое число n (2 6 n 6 1018). Формат выходных данных Для каждого теста вывести одно число — искомое количество способов. Система оценивания Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Задача 3. Робот-пылесос. Рассмотрим координатную плоскость, которую планируется очищать с использованием робота пылесоса. Робот-пылесос представляет собой квадрат размером k ×k со сторонами, параллельными осям координат. Изначально левый нижний угол робота находится в точке (0, 0), а правый верхний, соответственно — в точке (k, k). Вам дана последовательность из n перемещений робота по плоскости, i-е перемещение характеризуется направлением di , принимающим значения ‘N’ (вверх, увеличение координаты Y ), ‘S’ (вниз, уменьшение координаты Y ), ‘W’ (влево, уменьшение координаты X) или ‘E’ (вправо, увеличение координаты X), и целым числом ai — расстоянием, на которое робот перемещается. Робот в каждый момент времени убирает всю площадь под собой. Иными словами, точка считается убранной тогда и только тогда, когда она в какой-то момент времени принадлежала квадрату размера k × k, на котором находился робот. По заданным перемещениям робота посчитайте суммарную площадь всей убранной поверхности.
Задача 4. Разноцветные точки. Рассмотрим n точек на плоскости, пронумерованных от 1 до n, обозначим их как P1, P2, . . . , Pn, координаты i-й точки (xi , yi). Рассмотрим следующий процесс. Выберем номер начальной точки i и номер следующей за ней точки j (i 6= j), а также целое число t. После этого номер прицельной точки k вычисляется по следующему алгоритму. Рассмотрим вектор −−→PiPj , направленный из точки Pi в точку Pj . Упорядочим все точки, кроме j-й, по углу, отсчитывая против часовой стрелки от направления вектора, равного −−→PiPj , отложенного из точки j. При равенстве угла будем упорядочивать точки по возрастанию расстояния до точки j. В качестве точки k выбирается точка, являющаяся t-й в данном порядке при нумерации с единицы. Далее точка j становится начальной, а точка k — следующей за ней, после чего, пользуясь тем же алгоритмом, вычисляется номер прицельной точки. Этот процесс повторяется до бесконечности. Для лучшего понимания процесса рассмотрим следующий пример. Пусть имеются 6 точек, изображенных на рисунке 1, а t = 4. Пусть номер начальной точки равен 1, а номер следующей за ней точки равен 2. Отложим вектор −−−→P1P2 от точки P2 и отсортируем все точки, кроме точки P2, по углу, отсчитывая против часовой стрелки от направления данного вектора. На рисунке 2 отложенный вектор обозначен пунктирной линией, а также для удобства проведены векторы из точки P2 во все остальные точки.
Точки будут упорядочены следующим образом: P3, P5, P1, P6, P4. Таким образом, номер прицельной точки равен 6. Далее точка 2 становится начальной, а точка 6 — следующей. На рисунке 3 изображен процесс для начальной точки 2 и следующей точки 6. Точки будут упорядочены следующим образом: P4, P3, P2, P1, P5. Обратите внимание, что точка P1 в этом списке находится раньше, чем точка P5, так как расстояние от точки P1 до точки P6 меньше, чем расстояние от точки P5 до точки P6. Прицельная точка будет иметь номер 1.
На рисунке 4 изображен процесс для начальной точки 6 и следующей точки 1. Обратите внимание, что в данном случае вектор −−−→P6P1, отложенный из точки P1 совпадает с вектором −−−→P1P5, отложенным из точки P1. Эти векторы изображены сплошной линией. Точки будут упорядочены следующим образом: P5, P6, P4, P2, P3. Прицельная точка будет иметь номер 2. Таким образом, далее процесс начнется для начальной точки 1 и следующей точки 2 и зациклится.
Задача 5. Метрострой Буровая установка «Нора 2022» для прокладки туннелей метро Битска имеет n двигателей. Питание установки устроено таким образом, что на все двигатели подается одно и то же целочисленное напряжение x. У каждого двигателя есть два режима, если на него подается напряжение x, то i-й двигатель работает в первом режиме, если x 6 zi и во втором режиме, если x > zi . При этом i-й двигатель характеризуется удельной мощностью ai в первом режиме и bi во втором режиме. Это означает, что увеличение напряжения на 1 когда двигатель находится в первом режиме, приводит к увеличению его мощности на ai , а во втором режиме приводит к увеличению его мощности на bi . Иначе говоря, при подаче напряжения x, если i-й двигатель находится в первом режиме он работает с мощностью aix, а если во втором режиме, то с мощностью aizi + bi(x − zi). Для прокладки туннеля суммарная мощность двигателей должна быть не меньше p. Какое минимальное целочисленное напряжение необходимо подать на установку, чтобы суммарная мощность двигателей была больше или равна p?
Задача 6. Красивые последовательности Дано множество A, элементами которого являются различные целые числа от 1 до 8. Рассмотрим последовательность [a1, a2, . . . , an] из n целых чисел, каждое из которых выбрано из множества A. Будем называть эту последовательность красивой, если для любого числа x все элементы последовательности, равные x, находятся на расстоянии не меньше x друг от друга. Иначе говоря, для любого числа x и для любых двух индексов 1 6 i < j 6 n, таких, что ai = aj = x, должно выполняться неравенство j − i > x. Требуется посчитать количество красивых последовательностей для заданного числа n и множества A, и вывести остаток от деления этого количества на число 109 + 7.
Задача 7. Камни Перед Бобом выложены в ряд n черных камней, пронумерованных от 1 до n. На i-м камне записано целое число ai . Для каждого числа от 1 до n известно, что оно записано ровно на одном камне, иными словами числа ai образуют перестановку. Будем называть соседними для i-го камня (i − 1)-й и (i + 1)-й камни (если они существуют). Боб выполняет следующие n шагов: • На первом шаге Боб выбирает произвольное i от 1 до n и красит i-й камень в белый цвет. • На шагах с номерами от 2 до n Боб смотрит на такие черные камни, которые являются соседними для хотя бы одного белого камня, из них он выбирает камень j с минимальным aj и красит его в белый цвет. Несложно заметить, что к концу выполнения всех шагов перед Бобом будут лежать n белых камней. Алиса выбрала q пар значений pj и kj . Для каждой пары она хочет выяснить, сколько существует различных способов выбрать камень на первом шаге, которые приведут к тому, что камень с номером pj станет белым ровно на kj -м шаге. Помогите Бобу ответить на q запросов Алисы.
Задача 8. Обыкновенная задача про строки Назовем две строки s и t эквивалентными, если для любой строки u длины 2, количество вхождений u в s совпадает с количеством вхождением u в t. Таким образом, строки «aaaba», «abaaa» и «baaab» попарно эквивалентны между собой (строка «aa» входит два раза, строка «ab» один раз, строка «ba» один раз, строка «bb» не входит как подстрока), а строки «abb» и «bba» — нет. В этой задаче вам будут даны q строк, состоящих из символов «a», «b» и «c», для каждой из которых надо будет посчитать количество эквивалентных им непустых строк, также состоящих из символов «a», «b» и «c». Так как это количество может быть очень большим, то надо вывести его остаток от деления на 109 + 7.