Муниципальный этап ВсОШ по информатике 2026, 9-11 классы, Вологодская область и Краснодарский край
1. Места в поезде «Ласточка»
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В новом вагоне для поезда «Ласточка» нумерация мест показана на схеме:

$$$\fbox{ 1 }$$$ $$$\fbox{ 5 }$$$$$$\fbox{13}$$$ $$$\fbox{17}$$$$$$\fbox{25}$$$ $$$\fbox{29}$$$...
$$$\fbox{ 2 }$$$ $$$\fbox{ 6 }$$$$$$\fbox{14}$$$ $$$\fbox{18}$$$$$$\fbox{26}$$$ $$$\fbox{30}$$$...
$$$\fbox{ 4 }$$$ $$$\fbox{ 8 }$$$$$$\fbox{16}$$$ $$$\fbox{20}$$$$$$\fbox{28}$$$ $$$\fbox{32}$$$...
проход
$$$\fbox{10}$$$ $$$\fbox{12}$$$$$$\fbox{22}$$$ $$$\fbox{24}$$$$$$\fbox{34}$$$ $$$\fbox{36}$$$...
$$$\fbox{ 9 }$$$ $$$\fbox{11}$$$$$$\fbox{21}$$$ $$$\fbox{23}$$$$$$\fbox{33}$$$ $$$\fbox{35}$$$...

Согласно схеме, с одной стороны от прохода располагаются боксы по 6 мест, с другой стороны — боксы по 4 места. Все нечётные места расположены у стен вагона (у окон). При этом некоторых мест не существует — например, нет мест 3, 7, 15, 19 и так далее. Закономерность, по которой нумерация продолжается дальше, можно понять из схемы.

Вася купил билет на место номер $$$x$$$. Перечислите другие места в том же боксе, что и место $$$x$$$, чтобы Петя выбрал себе место по соседству с Васей.

Входные данные

Вводится единственное целое число $$$x$$$  — номер Васиного места ($$$1 \leq x \leq 10^9$$$).

Выходные данные

Выведите несколько целых чисел  — все другие номера мест, расположенных в том же боксе, что и место $$$x$$$. Номера требуется вывести в возрастающем порядке. Если Вася ошибся, когда сообщал номер Пете, и место с номером $$$x$$$ не существует, то выведите -1.

Система оценки

Решения, работающие при $$$x \le 36$$$, будут оцениваться в 50 баллов.

Примеры
Входные данные
6
Выходные данные
1 2 4 5 8 
Входные данные
21
Выходные данные
22 23 24 
Входные данные
3
Выходные данные
-1

2. Разделение Фибоначчи
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность Фибоначчи начинается с чисел $$$F_1=1$$$, $$$F_2=1$$$. Каждое следующее число равно сумме двух предыдущих. Индексация начинается с единицы.

Нужно построить ряд из $$$n$$$ чисел с одним перезапуском после позиции $$$i$$$: то есть сначала записываются $$$i$$$ первых чисел Фибоначчи ($$$ 2 \leq i \leq n - 2$$$), а затем последовательность начинается заново с $$$F_1$$$ и $$$F_2$$$ и продолжается по тому же правилу, пока в ряду не станет ровно $$$n$$$ чисел.

Выберите значение $$$i$$$ так, чтобы сумма всех $$$n$$$ чисел была наименьшей. Если несколько позиций дают одинаковую сумму, выберите наименьшее $$$i$$$.

Входные данные

Одно целое число $$$n$$$ ($$$6 \le n \le 80$$$).

Выходные данные

В первой строке выведите выбранную позицию $$$i$$$. Во второй строке выведите $$$n$$$ чисел полученного ряда через пробел.

Система оценки

Каждый пройденный тест даёт одинаковое количество баллов, полное решение получает 100 баллов.

Примеры
Входные данные
6
Выходные данные
3
1 1 2 1 1 2
Входные данные
7
Выходные данные
3
1 1 2 1 1 2 3
Примечание

Обратите внимание, что ответ может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битный целочисленный тип данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). В языке Python ничего дополнительно делать не требуется.

3. РобоЁжики
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Безумный гений доктор Шпунтик собирает армию боевых роботов-ёжиков из старого металлолома. Перед ним лежит огромная железная конструкция: $$$n$$$ круглых деталей-шестерёнок, которые соединены $$$m$$$ стальными прутьями (каждый прут соединяет ровно две детали). Чтобы активировать одного робота-ёжика, доктору нужно выбрать ровно одну деталь и несколько стальных прутьев, приваренных к этой детали (они станут «иголками»). Для того чтобы робот-ёжик считался правильным и готовым к работе, у него должно быть как минимум три иголки.

Шпунтику не нравится однообразная работа, поэтому каждый его робот должен быть уникальным. Два робота-ёжика считаются различными, если для них выбраны разные детали, или если у них отличается хотя бы одна иголка (выбраны разные наборы прутьев, торчащих из детали). Доктор хочет вычислить, сколько всего различных правильных роботов-ёжиков скрыто в его конструкции. Ёжиков настолько много, что без помощи Шпунтику не справиться. Так как количество роботов может быть очень большим, выведите ответ по модулю $$$10^9 + 7$$$.

Формально: вам дан неориентированный граф. Требуется вычислить количество подграфов вида «ёжик»: в них центральная вершина связана рёбрами с несколькими другими количеством не менее трёх, и других рёбер нет. Обратите внимание: в исходном графе вершины – концы «иголок» «ёжика» могут быть связаны рёбрами, просто при выделении подграфа «ёжик» они в него не включаются. «Ёжики» считаются различными, если есть хотя бы одна вершина, присутствующая в одном из них и отсутствующая в другом. Вам требуется вычислить остаток от деления количества «ёжиков» на число $$$10^9 + 7.$$$

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$n - 1 \le m \le 3 \cdot 10^5$$$) — количество деталей и прутьев в конструкции соответственно. В следующих $$$m$$$ строках содержатся описания прутьев. Каждая строка содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — начало и конец прута. Гарантируется, что конструкция связная и описания прутьев не повторяются.

Выходные данные

Выведите одно целое число — количество различных роботов-ёжиков в заданной конструкции по модулю $$$10^9 + 7$$$ (то есть остаток от деления на $$$10^9 + 7$$$).

Система оценки

Подзадача 1 (до 20 баллов): $$$n, m \le 15$$$

Подзадача 2 (до 24 баллов): $$$n, m \le 2000$$$

Подзадача 3 (до 56 баллов): $$$n, m \le 3 \cdot 10^5$$$

Примеры
Входные данные
4 3
1 2
1 3
1 4
Выходные данные
1
Входные данные
5 4
1 2
1 3
1 4
1 5
Выходные данные
5
Примечание

Примечание по языку Python. Два числа, записанных через пробел, можно прочитать так:

n, m = map(int, input().split())

4. Красивый отчёт
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана информация о прибыли IT-компании за $$$n$$$ подряд идущих дней. Для красивого отчёта требуется выбрать из них максимальное количество дней так, чтобы выполнялись следующие два условия:

  • В каждый следующий день прибыль должна быть больше, чем в предыдущий.
  • Наименьшее и наибольшее расстояния между соседними днями должны отличаться не более чем на единицу.
Входные данные

В первой строке входных данных записано целое число $$$n$$$ ($$$1 \le n \le 10^4$$$).

В следующих $$$n$$$ строках записаны целые числа в диапазоне от $$$0$$$ до $$$10^5$$$ — прибыль компании в каждый из $$$n$$$ дней.

Выходные данные

Выведите одно целое число — максимальное количество дней в отчёте.

Система оценки

Подзадача 1 (до 50 баллов): $$$n \le 10$$$

Подзадача 2 (до 50 баллов): $$$n \le 5000$$$

Примеры
Входные данные
7
4
2
1
3
1
0
5
Выходные данные
3
Входные данные
3
3
2
1
Выходные данные
1
Примечание

В первом примере можно выбрать для отчёта дни с номерами 2, 4, 7.

5. Бабушкино варенье
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бабушка хранит варенье в длинной ёмкости, разделённой на $$$N$$$ последовательных секций. В секции с номером $$$i$$$ находится $$$a_i$$$ единиц варенья.

Бабушка выбирает непустой участок из подряд идущих секций — с $$$i$$$-й по $$$j$$$-ю включительно — и сливает из него всё варенье в банки (она выполняет это один раз). Границами участка могут служить перегородки между секциями или края ёмкости.

Объём одной банки равен $$$M$$$. Бабушка заполняет только целые банки, а варенье, которого не хватило на следующую полную банку, выбрасывает.

Найдите минимальное количество варенья, которое придётся выбросить.

Входные данные

В первой строке записаны два целых числа $$$N$$$ и $$$M$$$ ($$$1 \le N \le 2\,000\,000$$$, $$$N \lt M \le 10\,000\,001$$$).

Во второй строке записаны $$$N$$$ целых чисел $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \le a_i \le 10^9$$$).

Выходные данные

Выведите одно целое число — минимальное количество выброшенного варенья.

Система оценки

Подзадача 1 (до 30 баллов): $$$N \le 2\,000$$$.

Подзадача 2 (до 30 баллов): $$$N \le 200\,000$$$.

Подзадача 3 (до 40 баллов): без дополнительных ограничений.

Примеры
Входные данные
3 10
5 8 6
Выходные данные
3
Входные данные
1 2
2
Выходные данные
0
Входные данные
1 10000001
1000000000
Выходные данные
9999901
Примечание

В задачу были добавлены дополнительные тесты, которых не было во время олимпиады.

Примечание для пишущих на Python. Набор целых чисел, записанных через пробел, можно прочитать так:

a = [int(x) for x in input().split()]

Примечание по быстрому вводу. В последней подзадаче нужно вводить большой объём данных. В некоторых языках для этого нужно использовать специальные способы ускорения ввода.

В языке C++ достаточно добавить в начало функции main следующие строки:

ios_base::sync_with_stdio(false); 
cin.tie(0);

В Java используйте 'BufferedInputStream' и считывайте целые числа из байтов. 'Scanner' на большом входе может работать слишком медленно.

В C# используйте 'BufferedStream' поверх 'Console.OpenStandardInput()' и считывайте целые числа из байтов. Чтение всей строки через 'Console.ReadLine().Split()' создаёт много строк и может потребовать слишком много времени и памяти.

Пишущим на языке Python рекомендуется сдавать эту задачу на PyPy.