Муниципальный этап ВсОШ по информатике в Липецкой области 2025 (9-11 классы)
Statement is not available in English language
1. Коллекция фотографий
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Всего у Егора получилось $$$a + b$$$ фотографий, из которых $$$a$$$ имеют большой размер, а $$$b$$$ — маленький. На каждой странице фотоальбома можно разместить либо одну любую фотографию, либо две маленькие фотографии. При этом один фотоальбом содержит $$$n$$$ страниц. Для того чтобы все получилось красиво, Егор планирует клеить фотографии на каждую страницу только с одной стороны.

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

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — количество страниц в каждом фотоальбоме.

Вторая строка содержит одно целое число $$$a$$$ ($$$0 \le a \le 10^{18}$$$) — количество больших фотографий.

Третья строка содержит одно целое число $$$b$$$ ($$$0 \le b \le 10^{18}$$$) — количество маленьких фотографий.

Гарантируется, что $$$a + b \ge 1$$$, то есть у Егора есть хотя бы одна фотография.

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

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

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

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

Помимо тестов из условия, данная задача содержит $$$20$$$ тестов, каждый из которых будет независимо оцениваться в $$$5$$$ баллов.

Решения, верно работающие при $$$n, a, b \le 1\,000$$$, получат не менее $$$25$$$ баллов.

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

В первом примере у Егора есть $$$3$$$ большие и $$$2$$$ маленькие фотографии. Маленькие фотографии можно объединить на одной странице, а каждая большая фотография будет занимать отдельную страницу. Таким образом, для размещения всех фотографий достаточно четырех страниц. Это значит, что достаточно купить ровно один фотоальбом.

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

В третьем примере все фотографии являются маленькими, поэтому их можно сгруппировать на четырех страницах.

Statement is not available in English language
2. Саша и разнообразные числа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Саша считает натуральное число разнообразным, если все цифры в его десятичной записи попарно различны. Например, числа $$$5$$$, $$$827$$$ и $$$12\,345\,678$$$ являются разнообразными, а числа $$$33$$$, $$$2\,025$$$ и $$$998\,244\,353$$$ — не являются.

Сегодня Саша отпраздновал свой $$$n$$$-й день рождения, и ему стало интересно, чему равно минимальное разнообразное число, большее чем $$$n$$$. Помогите Саше ответить на этот вопрос.

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

Единственная строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

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

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

Выведите одно целое число — минимальное разнообразное число, большее $$$n$$$. Если не существует ни одного разнообразного числа, большего $$$n$$$, выведите число $$$-1$$$.

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

Помимо тестов из условия, данная задача содержит $$$20$$$ тестов, каждый из которых будет независимо оцениваться в $$$5$$$ баллов.

Примеры
Входные данные
1
Выходные данные
2
Входные данные
121
Выходные данные
123
Входные данные
998244353
Выходные данные
1023456789

Statement is not available in English language
3. Беспорядок в библиотеке
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В университетской библиотеке есть полка, на которой расположены $$$n$$$ книг. Каждая книга на этой полке — один из трех томов легендарной серии «Искусство программирования». Однако книги на полке никак не упорядочены, что усложняет процесс их выдачи читателям. Для решения этой проблемы руководство библиотеки приобрело робота, который может выполнять примитивные операции, описанные далее.

Для удобства пронумеруем все книги на полке слева направо числами от $$$1$$$ до $$$n$$$. За одну операцию робот может проехать вдоль полки слева направо и забрать с полки $$$1$$$-й, $$$2$$$-й и $$$3$$$-й тома в таком порядке. Иными словами, робот выберет некоторые книги с номерами $$$i$$$, $$$j$$$ и $$$k$$$ ($$$1 \le i \lt j \lt k \le n$$$), такие что $$$i$$$-я книга является $$$1$$$-м томом, $$$j$$$-я книга является $$$2$$$-м томом, а $$$k$$$-я книга является $$$3$$$-м томом.

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

Ваша задача — найти максимальное количество томов, которые сможет забрать робот, выполнив некоторое количество описанных операций.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — количество книг на полке.

Вторая строка состоит из $$$n$$$ символов «1», «2» и «3», где $$$i$$$-й символ обозначает номер $$$i$$$-го тома.

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

Выведите одно целое число — максимальное количество томов, которые сможет забрать робот, выполнив некоторое количество описанных операций.

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

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
00Тесты из условияполная
15$$$n \le 3$$$первая ошибка
210 Гарантируется, что ответ не превосходит $$$3$$$ 1первая ошибка
310 Гарантируется, что ответ равен $$$0$$$ или $$$n$$$ 1первая ошибка
45 Гарантируется, что исходный порядок книг на полке выглядит как $$$11 \ldots 122 \ldots 2 33 \ldots 3$$$ (некоторые тома могут отсутствовать) первая ошибка
510$$$n \le 15$$$1первая ошибка
625$$$n \le 1\,000$$$1, 5первая ошибка
735нет1 – 6первая ошибка
Примеры
Входные данные
8
12123132
Выходные данные
6
Входные данные
3
123
Выходные данные
3
Входные данные
4
1311
Выходные данные
0
Входные данные
3
132
Выходные данные
0
Примечание

Рассмотрим первый пример. Сначала робот может забрать книги с номерами $$$1$$$, $$$2$$$ и $$$7$$$. После этого книжная полка будет выглядеть так: __1231_2 (здесь символом «_» обозначено пустое место). Затем робот может забрать книги с номерами $$$3$$$, $$$4$$$ и $$$5$$$. После этого книжная полка будет выглядеть так: _____1_2.

Во втором примере робот за одну операцию заберет все книги.

В третьем примере робот не сможет выполнить ни одну операцию, так как на полке нет $$$2$$$-го тома.

В четвертом примере робот не сможет выполнить ни одну операцию, так как книги на полке находятся в таком порядке, что робот не сможет забрать сначала $$$1$$$-й, затем $$$2$$$-й, после чего $$$3$$$-й том.

Statement is not available in English language
4. Время волшебства
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, Новый год — время волшебства. В этот раз вас ждут целых два волшебных подарка: муниципальный этап и таблица $$$a$$$ размером $$$n \times m$$$, состоящая из строчных латинских букв. Пронумеруем строки числами от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы — слева направо числами от $$$1$$$ до $$$m$$$. Клетка, находящаяся на пересечении $$$i$$$-й строки и $$$j$$$-го столбца, имеет координаты $$$(i, j)$$$.

Рассмотрим произвольную клетку $$$(i, j)$$$ и натуральное число $$$k$$$. Скажем, что в клетке $$$(i, j)$$$ начинается елка высоты $$$k$$$, если следующие элементы таблицы совпадают:

  • символ $$$a_{i, j}$$$;
  • символы $$$a_{i+1,j-1}, a_{i+1,j}, a_{i+1,j+1}$$$;
  • символы $$$a_{i+2,j-2}, a_{i+2,j-1}, a_{i+2,j}, a_{i+2,j+1}, a_{i+2,j+2}$$$;
  • и так далее, символы $$$a_{i+k-1,j-k+1}, a_{i+k-1,j-k+2}, \ldots, a_{i+k-1,j+k-2}, a_{i+k-1,j+k-1}$$$.

Визуально елку высоты $$$k$$$ можно представить как заштрихованную область на рисунке. Символы во всех заштрихованных клетках должны быть попарно равны.

Пример елки с $$$k = 5$$$

Ваша задача — найти, какой максимальной высоты елка присутствует в таблице $$$a$$$.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 5\,000$$$) — размеры таблицы.

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ строчных латинских букв — элементы таблицы $$$a$$$.

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

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

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

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
00Тесты из условияполная
110$$$n, m \le 50$$$первая ошибка
215$$$n, m \le 100$$$1первая ошибка
320$$$n, m \le 300$$$1, 2первая ошибка
420$$$n, m \le 500$$$1, 2, 3первая ошибка
510 Гарантируется, что таблица состоит из одинаковых букв первая ошибка
625нет1 – 5первая ошибка
Примеры
Входные данные
5 5
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
Выходные данные
3
Входные данные
7 8
yewqloec
truhfkdb
daabbnfm
szbbbbbn
szbbbbbm
dbbbbbbb
azzzzzzz
Выходные данные
4
Примечание

В первом примере елка высоты $$$3$$$ начинается в символе $$$(1, 3)$$$.

Во втором примере елка высоты $$$4$$$ начинается в символе $$$(3, 5)$$$.

Statement is not available in English language
5. Подпись Николая
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Николай — известный художник, он рисует картинки в стиле пиксель-арт. Недавно он нарисовал картинку размером $$$n \times m$$$ пикселей, используя палитру из $$$26$$$ цветов. Каждый цвет обозначается строчной латинской буквой.

Ясно, что любой художник постарается оставить подпись на своей картине. Николай решил оставить свою подпись в виде буквы «N». Буквой «N» называется множество клеток одинакового цвета, которое можно вписать в квадрат так, чтобы множество состояло из первого и последнего столбцов квадрата, а также содержало все клетки на главной диагонали этого квадрата (см. картинки).

Примеры множеств, которые являются буквой «N».
Примеры множеств, которые не являются буквой «N».

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

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

В первой строке содержится пара натуральных чисел $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 4 \cdot 10^6$$$, $$$1 \le n \cdot m \le 4 \cdot 10^6$$$) — высота и ширина картины.

В следующих $$$n$$$ строках содержится по $$$m$$$ строчным латинским буквам — картина Николая.

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

Выведите единственное число — ответ на задачу.

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

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
00Тесты из условияполная
15 Таблица состоит из одинаковых символов первая ошибка
27 В каждой строке все символы одинаковые 1первая ошибка
38$$$n \le 2$$$первая ошибка
49$$$n \le 3$$$3первая ошибка
517$$$n, m \le 50$$$первая ошибка
621$$$n \cdot m \le 200\,000$$$5первая ошибка
733нет1 – 6первая ошибка
Пример
Входные данные
4 4
gyyg
ggyg
gcgg
grbg
Выходные данные
17
Примечание

В приведенном примере есть $$$16$$$ букв «N» размером $$$1 \times 1$$$ и одна буква «N» размером $$$4 \times 4$$$.

Ни одна из букв «N» вписанных в квадраты $$$3 \times 3$$$ или квадраты $$$2 \times 2$$$ не является одноцветной, поэтому в ответе они не учитываются.