410515: GYM104031 E Котики
Description
Осень — время, когда хочется чего-нибудь тёплого. Кеша иногда заходит в котокафе, чтобы выпить горячего кофе и, конечно, погладить котиков. Котиков в кафе достаточно много, притом разных мастей. Иногда Кеша пытается их пересчитать, но это не так-то просто.
В одно из своих посещений кафе Кеша проанализировал процесс глажения котиков.
Кеша гладил каждого котика в течение одной минуты. После этого котик мог либо уйти, либо подождать какое-то время, чтобы его погладили снова. Кеша заметил, что никакой котик не ждал более, чем $$$m$$$ минут, а также что никакого котика он не гладил более одной минуты подряд.
Известен список мастей котиков, которых гладил Кеша, в том порядке, в котором он их гладил. Ваша задача — определить минимально возможное количество котиков, которых погладил Кеша. Также, полагая, что котиков было минимальное возможное количество, нужно определить максимальное количество котиков одной масти, которых погладил Кеша.
Входные данныеВ первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество записей в списке мастей.
Во второй строке содержится целое число $$$m$$$ $$$(1 \le m \le 10^5)$$$ — максимально возможное время ожидания котиком очередного поглаживания.
В каждой из следующих $$$n$$$ строк содержится по одной масти котика. Масть — непустая последовательность строчных символов латинского алфавита длиной не более $$$30$$$.
Выходные данныеВ первой строке выведите целое число — минимально возможное количество котиков, которых погладил Кеша.
Во второй строке выведите целое число — максимальное количество котиков одной масти, которых погладил Кеша.
Система оценкиВ первых пяти подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов.
Баллы за шестую подзадачу начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены
Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 1 (до 10) | $$$n \le 100$$$, $$$m = 1$$$, масть котика — | нет | полная |
| строка длиной $$$1$$$ символ | ||||
| 2 | 1 (до 10) | $$$n \le 100$$$, $$$m \le 10$$$, масть котика — | 1 | полная |
| строка длиной $$$1$$$ символ | ||||
| 3 | 2 (до 20) | $$$n \le 10^5$$$, $$$m \le 10^5$$$, масть котика — | 2 | полная |
| строка длиной $$$1$$$ символ | ||||
| 4 | 2 (до 10) | $$$n \le 10^5$$$, $$$m \le 10^5$$$, | 1 | полная |
| котики только $$$2$$$ мастей | ||||
| 5 | 2 (до 10) | $$$n \le 10^5$$$, $$$m \le 10^5$$$, | 1 | полная |
| котики только $$$3$$$ мастей | ||||
| 6 | 0 (40) | $$$n \le 10^5$$$, $$$m \le 10^5$$$ | 3, 4, 5 | первая ошибка |
14 3 gray white red gray cream white white red tabby black white black red grayВыходные данные
10 3Примечание
Сначала Кеша гладил серого кота, затем — белого, затем — рыжего, и после этого — снова серого кота. Это мог быть первый серый кот, поскольку в этом случае ему пришлось бы ждать $$$2$$$ минуты. Таким образом, минимальное количество различных котов, которых погладил Кеша к этому моменту, составляет $$$3$$$.
После серого кота Кеша погладит кота кремового окраса, а затем белого. Белый кот мог быть «прошлым» белым котом, поскольку он мог ждать $$$3$$$ минуты. Как можно видеть, в списке два подряд кота белой масти, и это разные коты (поскольку ни одного кота Кеша не гладил более одной минуты подряд). К этому моменту Кеша погладит ещё двух «новых» котов, итого их станет $$$5$$$. Заметим, что два белых кота — это пока максимальное количество котов одной масти.
Далее Кеша гладит рыжего кота, но это не может быть рыжий кот, которого он гладил третьим по счёту — прошло уже более $$$3$$$ минут. Это значит, что Кеша погладил уже двух рыжих котов, а минимальное количество различных котов, которых погладил Кеша, составляет теперь $$$6$$$.
После рыжего кота Кеша гладит кота расцветки табби, затем чёрного кота, и снова белого кота. Это мог быть второй белый кот, которого уже гладил Кеша, поскольку кот мог ожидать в течение $$$3$$$ минут. Следовательно, минимальное количество различных котов, которых погладил Кеша, теперь равно $$$8$$$.
Следующий кот, которого гладит Кеша, имеет чёрный окрас, и это может быть тот черный кот, которого он гладил перед белым. Минимальное количество различных котов, которых погладил Кеша, не увеличилось.
После этого Кеша гладит рыжего и серого котов, гладить которых до этого он не мог. Поэтому минимальное количество различных котов, которых погладил Кеша, составляет $$$10$$$, а максимальное количество котов одной масти будет равно $$$3$$$, поскольку Кеша погладил уже третьего рыжего кота.