- Описание
- Отправленные решения
583. Тяп-ляп, фигак, в релиз!
Вы долго об этом мечтали и наконец устроились работать в крупную IT-компанию. Вы долго-долго учились всем существующим современным технологиям и уже готовы применить все свои знания на практике. Но тут вы садитесь за свой рабочий стол и видите лист с распечатанным крупными буквами девизом компании: abcdabcdabcdabcd...
.
В девизе компании указаны четыре главных принципа $-$ a
(Тяп), b
(Ляп), c
(Фигак) и d
(Релиз). Поэтому вы рассматриваете строки длины $n$, состоящие из указанных четырех букв латинского алфавита. Неупорядоченные пары букв «ab», «bc», «cd» и «da» в этом девизе соседние, поэтому будем называть такие пары символов хорошими. Итак, если вам дана строка $s$ длины $n$ и известно, что неупорядоченная пара символов $\{ x, y \}$ хорошая, то со строкой можно совершить одну из указанных операций:
- если $s_n = x$, то разрешается заменить этот символ на $y$,
- если существует такое $1 \le i < n$, что $s_i = x$ и $s_{i+1} = \ldots = s_n = y$, то разрешается заменить $i$-й символ строки на $y$, а все последующие $-$ на $x$.
Например, строку bacdd
можно заменить на одну из строк bacda
, bacdc
или badcc
, а строку aac
можно заменить на aab
или aad
.
Непустую последовательность операций для строки $s$ будем называть корректной, если выполняются следующие два условия:
- после совершения всех операций снова получится строка $s$,
- никакая строка, кроме $s$, в ходе совершения операций не возникнет более одного раза. При этом строка $s$ должна возникнуть ровно два раза $-$ перед началом выполнения операций и после выполнения всех операций.
Теперь мы готовы перейти к условию задачи! У вас есть множество строк, которое изначально пусто. Далее $q$ раз в множество добавится очередная строка $t_i$, либо строка $t_i$ удалится из множества. После каждого запроса требуется вывести минимальный и максимальный размер корректной последовательности операций, в ходе которой каждое слово возникает хотя бы один раз. Выбор начальной строки $s$ остается за вами.
Формат ввода
Первая строка содержит два целых числа $n$ и $q$ ($1 \le n \le 20$, $1 \le q \le 100\,000$) $-$ длина рассматриваемых строк и количество запросов изменения множества строк.
Каждая из следующих $q$ строк содержит строку $t_i$ ($\lvert t_i \rvert = n$). Все строки состоят из символов «a», «b», «c» и «d». Если до этого запроса строка $t_i$ не находилась в множестве, то она добавляется в него, а иначе она удаляется из множества.
Формат вывода
Для каждого из $q$ запросов выведите два целых числа $-$ минимальный и максимальный размер корректной последовательности операций, в ходе которой каждое слово из множества возникает хотя бы один раз.
Если не существует ни одной последовательности операций, удовлетворяющей условию задачи, выведите одно число $-1$.
Примечание
Рассмотрим первый пример.
- После первого запроса множество строк равно $\{$\texttt{aa}$\}$, минимальная последовательность действий имеет следующий вид:
aa, ab, aa
. В качестве максимальной последовательности действий подходитaa, ab, ba, bb, bc, cb, cc, cd, dc, dd, da, ad, aa
. - После второго запроса множество строк равно
aa, ac
. Минимальная и максимальная последовательности действий:aa, ab, ac, ad, aa
. - После третьего запроса множество строк равно
aa, ac, dd
. Не существует последовательности действий, которая подходит под условие, поэтому следует вывести $-1$. - После четвертого запроса множество строк равно
aa, dd
. Минимальная и максимальная последовательности действий таковы:aa, ab, ba, bb, bc, cb, cc, cd, dc, dd, da, ad, aa
.
Ограничения
Ограничение времени
3 с
Ограничение памяти
1 ГБ
Пример 1
2 4
aa
ac
dd
ac
2 12
4 4
-1
12 12
Пример 2
3 2
acc
bdd
2 44
28 44