Муниципальный этап ВсОШ по информатике в Самаре 2025-2026 (9-11 классы)
A. Аудитория
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Фалалей стал студентом первого курса университета.

Университет представляет собой большое здание со множеством аудиторий. На каждом этаже есть аудитории трёх разных размеров: большие, средние и малые. Большие аудитории вмещают $$$100$$$ человек, средние — $$$50$$$ человек, а малые — $$$25$$$ человек.

Заметим, что есть ещё и технические помещения, и небольшие рекреации, но их мы рассматривать не будем. Количество аудиторий каждого вида — чётное.

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

Также в здании четыре лестницы. Лестница $$$\#1$$$ расположена между левым крылом и центральной частью, лестница $$$\#4$$$  — между правым крылом и центральной частью. Лестница $$$\#2$$$ расположена ближе к левому крылу, левее неё расположена треть малых аудиторий стороны этажа, примыкающей к лестнице, и четверть малых аудиторий противоположной стороны этажа. Лестница $$$\#3$$$ расположена ближе к правому крылу, правее неё также расположена треть малых аудиторий стороны этажа, примыкающей к лестнице, и четверть малых аудиторий противоположной стороны этажа.

Аудитории перенумерованы по направлению движения часовой стрелки. Первый номер имеет самая левая большая аудитория, расположенная по стороне этажа, противоположной лестницам.

Пример планировки этажа с двадцатью аудиториями показан на рисунке.

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

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

В первой строке содержится целое число $$$n$$$ $$$(20 \le n \le 2 \cdot 10^6)$$$ — общее количество аудиторий на этаже. Гарантируется, что количество аудиторий корректно и соответствует описанной планировке этажа.

Во второй строке содержится целое число $$$k$$$ $$$(1 \le k \le n)$$$ — номер аудитории, в которую нужно попасть Фалалею.

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

В первой строке выведите целое число $$$t$$$ — количество человек, которое вмещает аудитория: $$$100$$$, если аудитория большая, $$$50$$$ — если средняя, $$$25$$$ — если малая.

Во второй строке выведите целое число $$$l$$$ — номер лестницы, по которой следует подниматься Фалалею, чтобы оказаться как можно ближе к нужной аудитории (нумерация лестниц описана в условии).

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

В во всех трех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

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

Тесты из условия не оцениваются.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
11 (до 16)$$$n = 20$$$нетполная
24 (до 24)$$$n \le 1000$$$, $$$k \le n/2$$$1полная
34 (до 60)$$$n \le 2 \cdot 10^6$$$1, 2полная

Примеры
Входные данные
20
1
Выходные данные
100
1
Входные данные
20
5
Выходные данные
25
2
Входные данные
20
16
Выходные данные
25
3
Входные данные
20
12
Выходные данные
50
4
Примечание

Поясним приведённые примеры.

Во всех примерах на этаже $$$20$$$ аудиторий (что соответствует рисунку в задаче).

В первом примере Фалалею нужно попасть в аудиторию $$$\#1$$$, она является большой аудиторией (вмещает $$$100$$$ человек), а ближе всего к ней Фалалей окажется, если будет подниматься по первой лестнице ($$$1$$$ на второй строке).

Во втором примере Фалалею нужно попасть в аудиторию $$$\#5$$$, это малая аудитория (вмещает $$$25$$$ человек), а ближе всего к ней Фалалей окажется, если будет подниматься по второй лестнице ($$$2$$$ на второй строке).

В третьем примере Фалалею нужно попасть в аудиторию $$$\#16$$$, это малая аудитория (вмещает $$$25$$$ человек), ближе всего к ней Фалалей окажется, если будет подниматься по третьей лестнице ($$$3$$$ на второй строке).

В четвёртом примере Фалалею нужно попасть в аудиторию $$$\#12$$$, это средняя аудитория (вмещает $$$50$$$ человек), ближе всего к ней Фалалей окажется, если будет подниматься по четвёртой лестнице ($$$4$$$ на второй строке).

B. Шаг вперёд, три шага назад
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На занятии по программированию преподаватель предложил всем студентам для начала решить одну не очень сложную задачу. Конечно же, Фалалей захотел получить решение этой задачи с помощью новой версии большой языковой модели $$$BreadTHin$$$. Преподаватель, разумеется, говорил, что будет засчитывать только полностью самостоятельные решения, но Фалалей уверен, что решение $$$BreadTHin$$$ преподаватель не отличит от «человеческого».

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

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

Опишем происходящее более формально.

Пусть Фалалей только что отправил решение $$$\#(j-1)$$$, оно набрало $$$x_{j-1}$$$ баллов, и это больше, чем любое решение с меньшим номером. Будем называть это решение «лучшей попыткой».

Каждый раз, получая «лучшую попытку», Фалалей сразу же пытается её ещё улучшить и повторяет описанные ниже действия.

Фалалей просит $$$BreadTHin$$$ улучшить решение $$$\#(j-1)$$$, получает решение $$$\#j$$$, отправляет его на проверку, и это решение набирает $$$x_j$$$ баллов.

Если $$$x_{j} \le x_{j-1}$$$, Фалалей назовёт это решение «более плохим».

Фалалей готов сделать до трёх попыток улучшения «более плохого» решения.

Если в какой-либо из попыток $$$\#(j+k)$$$ $$$(k = 0, 1, 2, 3)$$$ Фалалей получит решение, набирающее $$$x_{j+k} \gt x_{j-1}$$$ баллов, то он назовёт это решение новой «лучшей попыткой» (и далее будет пытаться улучшать уже его).

Если же в ходе этих попыток получить новую «лучшую попытку» не удастся, Фалалей обратится к $$$BreadTHin$$$ с запросом на новое улучшение имеющейся «лучшей попытки» — решения $$$\#(j-1)$$$.

Более того, если в первой или второй попытке Фалалей получит решение, набирающее ещё меньше баллов, чем «более плохое» решение ($$$x_{j+k} \lt x_{j}, \, k = 1, 2$$$), то он обратится к $$$BreadTHin$$$ с запросом на новое улучшение решения $$$\#(j-1)$$$ (имеющейся «лучшей попытки») — сразу после этой попытки.

Ваша задача — определить количество решений, к которым возвращался Фалалей, номера этих решений, а также указать для каждого из этих решений, сколько раз он к нему возвращался. Известно, что ни одно из решений, отправленных Фалалеем на проверку, не набрало максимально возможное количество баллов.

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

В первой строке содержится целое число $$$n$$$ $$$(3 \le n \le 2 \cdot 10^5)$$$ — количество запросов к LLM, которое сделал Фалалей.

Далее в каждой строке содержится по одному целому числу $$$b_j$$$ $$$(0 \le b_j \le 10^6, \, j = 1, 2, \ldots, n)$$$, $$$b_j$$$ — количество баллов, набранное за решение $$$\#j$$$.

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

В первой строке выведите целое число $$$m$$$ — количество решений, к которым возвращался Фалалей.

Далее в каждой из $$$m$$$ строк выведите по два числа: номер решения, к которому возвращался Фалалей, и через пробел — количество раз, которое он к нему возвращался.

Выводите решения по порядку их номеров.

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

В первой, второй и третьей подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

Для решения второй подзадачи требуется, чтобы программа верно решала первую подзадачу.

В четвёртой подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Также для четвёртой подзадачи требуется, чтобы программа верно решала предшествующие подзадачи.

Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
11 (до 5)$$$n \le 5, \, b_j \le 10$$$нетполная
22 (до 20)$$$n \le 20, \, b_j \le 3$$$1полная
32 (до 10)$$$ b_j \le 1$$$нетполная
40 (65)любые допустимые значения1, 2, 3первая ошибка

Примеры
Входные данные
22
23
28
17
22
19
25
23
16
25
27
27
22
24
47
32
35
28
24
31
30
52
48
Выходные данные
2
2 3
14 1
Входные данные
5
72
57
64
68
62
Выходные данные
0
Примечание

Поясним приведённые примеры.

В первом примере происходит следующее.

Решение $$$\#1$$$ набирает 23 балла и сначала является (первой и единственной) лучшей попыткой. Однако первое же улучшение его — решение $$$\#2$$$ — даёт 28 баллов, и сразу же становится лучшей попыткой.

Теперь Фалалей запрашивает улучшение решения $$$\#2$$$. Полученное решение $$$\#3$$$ хуже, оно даёт только 17 баллов. Однако Фалалей попытается его улучшить. Первая такая попытка принесёт 22 балла, следующая — 19 баллов, и ещё одна — 25 баллов. Поскольку Фалалей ограничивается тремя попытками улучшить более плохое решение, то после этой попытки (решения $$$\#6$$$) он снова запросит улучшение решения $$$\#2$$$, и это будет первое возвращение к этому решению.

Решение $$$\#7$$$, являющееся улучшением решения $$$\#2$$$, даёт 23 балла. Фалалей попытается улучшить это решение, но уже следующая попытка (решение $$$\#8$$$) даст только 16 баллов, и Фалалей вновь запросит улучшение решения $$$\#2$$$. Это будет второе возвращение к этому решению.

Решение $$$\#9$$$, полученное в результате улучшения решения $$$\#2$$$, даст 25 баллов, следующие две попытки улучшить уже решение $$$\#9$$$ дадут по 27 баллов, а третья попытка — 22 балла. Так что к решению $$$\#2$$$ Фвлалаей вернётся в третий раз.

Решение $$$\#13$$$ даст 24 балла, но первая же попытка улучшить его станет лучшей попыткой из всех сделанных: решение $$$\#14$$$ даст 47 баллов. Теперь Фалалей попробует улучшать уже его.

Первое улучшение решения $$$\#14$$$ — решение $$$\#15$$$ даст 32 балла. Как обычно, Фалалей попробует улучшить его. Первая из таких попыток даст 35 баллов, а вторая — 28, что меньше даже 32. Поэтому Фалалей вернётся к решению $$$\#14$$$, и это будет первое такое возвращение.

Решение $$$\#18$$$ – новая попытка улучшить решение $$$\#14$$$ — даст 24 балла. Следующие две попытки улучшить решение $$$\#18$$$ дадут 31 и 30 баллов соответственно, а вот третья попытка (решение $$$\#21$$$) даст 52 балла и станет новой лучшей попыткой.

Фалалей запросит улучшение решения $$$\#21$$$, получит решение $$$\#22$$$, набирающее 48 баллов. На этом история запросов заканчивается, поэтому в качестве ответа мы выведем 2 решения: $$$\#2$$$ и $$$\#14$$$. К решению $$$\#22$$$ Фалалей возвращался трижды, а к решению $$$\#14$$$ — единожды.

Во втором примере Фалалей начинает с решения, набирающего 72 балла. Попытка улучшить его приводит к решению, набирающему 57 баллов. Следующие три попытки улучшения более плохого решения получают больше, чем 57 баллов каждая, но не более 72. Если бы он продолжал попытки, он вернулся бы решению, набравшему 72 балла. Но история запросов заканчивается, поэтому возвращения не происходит.

C. Сложный баланс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Фалалей хочет использовать большую языковую модель $$$BreadTHin$$$ для решения двух более сложных задач. Будем условно называть их $$$B$$$ и $$$C$$$.

Процесс решения каждой задачи выглядит следующим образом: Фалалей составляет запрос, отправляет его большой языковой модели $$$BreadTHin$$$, получает от неё результат в виде кода, отправляет код в проверяющую систему, получает сообщение о набранном количестве баллов.

Если это количество баллов не является максимально возможным, Фалалей вновь обращается к $$$BreadTHin$$$ с запросом на улучшение кода, и так далее.

Фалалей может сделать суммарно не более $$$n$$$ запросов $$$BreadTHin$$$.

Для каждой из задач известны $$$n$$$ чисел — количество баллов, которое Фалалей получит после очередного запроса в том порядке, в котором он их составляет. Порядок запросов изменяться не может. При решении каждой из задач Фалалей начинает с первого запроса для этой задачи, затем может перейти ко второму и так далее.

Известно, что ни один из запросов не приводит к получению максимально возможного количества баллов по задаче.

Ваша задача — определить, какое максимальное суммарное количество баллов может набрать Фалалей за эти две задачи и какое минимальное (суммарное по двум задачам) количество запросов ему для этого потребуется.

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

В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — количество запросов, имеющихся в распоряжении Фалалея.

Во второй строке содержится $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ $$$(0 \le b_i \le 10^9, \, i = 1, 2, \ldots, n)$$$, $$$b_i$$$ — количество баллов, которое Фалалей может получить за решение задачи $$$B$$$ после запроса $$$\#i$$$.

В третьей строке содержится $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ $$$(0 \le c_j \le 10^9, \, j = 1, 2, \ldots, n)$$$, $$$c_j$$$ — количество баллов, которое Фалалей может получить за решение задачи $$$C$$$ после запроса $$$\#j$$$.

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

Выведите три целых числа: максимальное суммарное количество баллов, которое может набрать Фалалей за эти две задачи, количество запросов, которое он при этом сделает по задаче $$$B$$$, и количество запросов, которое он при этом сделает по задаче $$$C$$$. Разделяйте числа пробелами или переводами строк.

Если существуют разные варианты ответов, выведите любой из них.

Обратите внимание, что суммарное количество запросов по задаче $$$B$$$ и задаче $$$C$$$ должно быть минимально возможным.

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

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

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

Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
12 (до 40)$$$n \le 1000, \, b_i, \, c_j \le 1000$$$нетполная
20 (60)любые допустимые значения1первая ошибка

Примеры
Входные данные
10
50 48 63 34 72 46 23 52 85 78
35 47 42 55 51 64 32 38 71 74
Выходные данные
127
3
6
Входные данные
3
25 58 92
34 67 88
Выходные данные
92
3
0
Входные данные
3
25 18 92
67 32 88
Выходные данные
92
1
1
Примечание

Поясним приведённые примеры.

В первом примере Фалалей может использовать три попытки для решения задачи $$$B$$$ (и получит за её решение 63 балла) и шесть попыток для решения задачи $$$C$$$ (и получит за её решение 64 балла). Всего он истратит 9 попыток из 10, дополнительная попытка не даст никакого улучшения.

Также правильным ответом будет пять попыток для решения задачи $$$B$$$ (что даст Фалалею 72 балла) и четыре попытки для решения задачи $$$C$$$ (Фалалей получит 55 баллов, в сумме 127 баллов). Суммарно он также потратит 9 попыток для получения 127 баллов.

Во втором примере Фалалей может получить максимальное количество баллов 92 за три попытки тремя способами: потратить все три попытки на решение задачи $$$B$$$; потратить на решение задачи $$$B$$$ две попытки, а на решение $$$C$$$ одну попытку; потратить на решение задачи $$$B$$$ одну попытку и на решение задачи $$$C$$$ две попытки. Любой из этих ответов будет верным.

В третьем примере Фалалей может получить 92 балла, либо потратив все три попытки на решение задачи $$$B$$$, либо потратив по одной попытке на решение каждой из задач. Поскольку во втором случае он потратит суммарно две попытки, это и будет единственным верным ответом (поскольку требуется минимизировать количество попыток).

D. От L до L и до M и обратно
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На занятии по иностранному языку преподаватель раздал студентам небольшие тексты, сообщив, что это фрагменты статей из научно-популярных журналов, и предложил в течение нескольких минут подготовить очень короткое изложение содержания этих фрагментов.

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

Фалалей утверждает, что если после вычеркивания из текста некоторых символов оставшиеся будут представлять собой последовательность $$$llmll$$$, то это и есть упоминание о большой языковой модели. Впрочем, он готов согласиться, что количество вычеркнутых символов между каждой из крайних букв $$$l$$$ и буквой $$$m$$$ не должно превосходить $$$k$$$.

Ваша задача — определить количество таких упоминаний в заданном тексте. Количество таких упоминаний может быть очень большим, поэтому ответ следует выводить по модулю $$$10^9 + 7$$$.

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

В первой строке содержится число $$$k$$$ $$$(1 \le k \le 2 \cdot 10^5)$$$ — максимально допустимое количество вычеркнутых символов между крайней буквой $$$l$$$ и буквой $$$m$$$.

Во второй строке содержится последовательность строчных латинских букв без пробелов. Длина последовательности не превосходит $$$2 \cdot 10^5$$$. Гарантируется, что в последовательности содержится хотя бы одна буква $$$m$$$.

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

Выведите одно целое число — количество упоминаний $$$llmll$$$ в тексте. Поскольку количество таких упоминаний может быть очень большим, выводите это число по модулю $$$10^9 + 7$$$.

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

В первых двух подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

В третьей и четвёртой подзадачах баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Для третьей и четвёртой подзадач требуется, чтобы программа верно решала предшествующие подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)($$$n$$$ — длина последовательности)
12 (до 10)$$$n \le 20$$$нетполная
22 (до 20)$$$n \le 1000, \, k = 1$$$нетполная
30 (30)$$$k \ge n/2$$$1, 2первая ошибка
40 (40)любые допустимые значения1, 2, 3первая ошибка

Примеры
Входные данные
3
alblmdllmleltle
Выходные данные
12
Входные данные
3
alaaaalmlbbbbbblb
Выходные данные
0
Входные данные
25
alaaaalmlbbbbbblb
Выходные данные
1
Примечание

Поясним приведённые примеры.

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

В первом примере упоминания будут следующие:

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

Во втором примере вычеркнуть не более 3 символов с каждой стороны от буквы $$$m$$$ недостаточно, чтобы получить хотя бы одно упоминание, поэтому ответ 0.

В третьем примере $$$k$$$ превосходит длину строки, поэтому, в отличие от предыдущего примера, можно вычеркнуть четыре буквы a слева и шесть букв b справа, чтобы получить llmll.