После поездки в отпуск у Егора на телефоне осталось большое количество красивых фотографий. Для того чтобы еще раз насладиться воспоминаниями о проведенном времени, он решил распечатать фотографии и вклеить их в винтажные фотоальбомы. Однако фотографий оказалось настолько много, что одного фотоальбома может и не хватить.
Всего у Егора получилось $$$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$$$ баллов.
432
1
323
2
507
1
В первом примере у Егора есть $$$3$$$ большие и $$$2$$$ маленькие фотографии. Маленькие фотографии можно объединить на одной странице, а каждая большая фотография будет занимать отдельную страницу. Таким образом, для размещения всех фотографий достаточно четырех страниц. Это значит, что достаточно купить ровно один фотоальбом.
Во втором примере нам необходимо потратить две страницы на размещение больших фотографий. После этого в фотоальбоме останется одна страница для размещения трех фотографий, чего недостаточно. Поэтому Егору придется купить второй фотоальбом.
В третьем примере все фотографии являются маленькими, поэтому их можно сгруппировать на четырех страницах.
Саша считает натуральное число разнообразным, если все цифры в его десятичной записи попарно различны. Например, числа $$$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
В университетской библиотеке есть полка, на которой расположены $$$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$$$-го тома.
Выведите одно целое число — максимальное количество томов, которые сможет забрать робот, выполнив некоторое количество описанных операций.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | 0 | Тесты из условия | полная | |
| 1 | 5 | $$$n \le 3$$$ | первая ошибка | |
| 2 | 10 | Гарантируется, что ответ не превосходит $$$3$$$ | 1 | первая ошибка |
| 3 | 10 | Гарантируется, что ответ равен $$$0$$$ или $$$n$$$ | 1 | первая ошибка |
| 4 | 5 | Гарантируется, что исходный порядок книг на полке выглядит как $$$11 \ldots 122 \ldots 2 33 \ldots 3$$$ (некоторые тома могут отсутствовать) | первая ошибка | |
| 5 | 10 | $$$n \le 15$$$ | 1 | первая ошибка |
| 6 | 25 | $$$n \le 1\,000$$$ | 1, 5 | первая ошибка |
| 7 | 35 | нет | 1 – 6 | первая ошибка |
812123132
6
3123
3
41311
0
3132
0
Рассмотрим первый пример. Сначала робот может забрать книги с номерами $$$1$$$, $$$2$$$ и $$$7$$$. После этого книжная полка будет выглядеть так: __1231_2 (здесь символом «_» обозначено пустое место). Затем робот может забрать книги с номерами $$$3$$$, $$$4$$$ и $$$5$$$. После этого книжная полка будет выглядеть так: _____1_2.
Во втором примере робот за одну операцию заберет все книги.
В третьем примере робот не сможет выполнить ни одну операцию, так как на полке нет $$$2$$$-го тома.
В четвертом примере робот не сможет выполнить ни одну операцию, так как книги на полке находятся в таком порядке, что робот не сможет забрать сначала $$$1$$$-й, затем $$$2$$$-й, после чего $$$3$$$-й том.
Как известно, Новый год — время волшебства. В этот раз вас ждут целых два волшебных подарка: муниципальный этап и таблица $$$a$$$ размером $$$n \times m$$$, состоящая из строчных латинских букв. Пронумеруем строки числами от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы — слева направо числами от $$$1$$$ до $$$m$$$. Клетка, находящаяся на пересечении $$$i$$$-й строки и $$$j$$$-го столбца, имеет координаты $$$(i, j)$$$.
Рассмотрим произвольную клетку $$$(i, j)$$$ и натуральное число $$$k$$$. Скажем, что в клетке $$$(i, j)$$$ начинается елка высоты $$$k$$$, если следующие элементы таблицы совпадают:
Визуально елку высоты $$$k$$$ можно представить как заштрихованную область на рисунке. Символы во всех заштрихованных клетках должны быть попарно равны.
Пример елки с $$$k = 5$$$ Ваша задача — найти, какой максимальной высоты елка присутствует в таблице $$$a$$$.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 5\,000$$$) — размеры таблицы.
Каждая из следующих $$$n$$$ строк содержит $$$m$$$ строчных латинских букв — элементы таблицы $$$a$$$.
Выведите одно целое число — высоту максимальной елки, которая есть в таблице.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | 0 | Тесты из условия | полная | |
| 1 | 10 | $$$n, m \le 50$$$ | первая ошибка | |
| 2 | 15 | $$$n, m \le 100$$$ | 1 | первая ошибка |
| 3 | 20 | $$$n, m \le 300$$$ | 1, 2 | первая ошибка |
| 4 | 20 | $$$n, m \le 500$$$ | 1, 2, 3 | первая ошибка |
| 5 | 10 | Гарантируется, что таблица состоит из одинаковых букв | первая ошибка | |
| 6 | 25 | нет | 1 – 5 | первая ошибка |
5 5aaaaaaaaaaaaaaaaaaaaaaaaa
3
7 8yewqloectruhfkdbdaabbnfmszbbbbbnszbbbbbmdbbbbbbbazzzzzzz
4
В первом примере елка высоты $$$3$$$ начинается в символе $$$(1, 3)$$$.
Во втором примере елка высоты $$$4$$$ начинается в символе $$$(3, 5)$$$.
Николай — известный художник, он рисует картинки в стиле пиксель-арт. Недавно он нарисовал картинку размером $$$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$$$ строчным латинским буквам — картина Николая.
Выведите единственное число — ответ на задачу.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | 0 | Тесты из условия | полная | |
| 1 | 5 | Таблица состоит из одинаковых символов | первая ошибка | |
| 2 | 7 | В каждой строке все символы одинаковые | 1 | первая ошибка |
| 3 | 8 | $$$n \le 2$$$ | первая ошибка | |
| 4 | 9 | $$$n \le 3$$$ | 3 | первая ошибка |
| 5 | 17 | $$$n, m \le 50$$$ | первая ошибка | |
| 6 | 21 | $$$n \cdot m \le 200\,000$$$ | 5 | первая ошибка |
| 7 | 33 | нет | 1 – 6 | первая ошибка |
4 4gyygggyggcgggrbg
17
В приведенном примере есть $$$16$$$ букв «N» размером $$$1 \times 1$$$ и одна буква «N» размером $$$4 \times 4$$$.
Ни одна из букв «N» вписанных в квадраты $$$3 \times 3$$$ или квадраты $$$2 \times 2$$$ не является одноцветной, поэтому в ответе они не учитываются.
![]() | ![]() |