Синее и лиловое
Задачу добавил: alef
Успешно сдано решений: 1
Время на тест - 1 с
И друзья Елисея, и Хасан успешно справились с заданиями Ормуса и добрались до еще одной залы, где увидели множество людей, часть из которых была одета в темно-синие плащи, а другая - в темно-лиловые. Человечек, сопровождавший друзей Елисея, попросил их немного подождать:
- Великий маг скоро закончит совещание со своими помощниками и примет вас. Он ждал вас, знал, что вы к нему придете, и скоро примет вас.
- А что означает цвет одежд помощников? - поинтересовался один из друзей Елисея.
- Это давняя, очень давняя традиция, никто даже не помнит, как она возникла. Никто, кроме, наверное, самого Ормуса, - отвечал человечек.
Человечек рассказал следующее. У Ормуса много помощников, и все они поделены на группы, состоящие не менее, чем из S человек, и не более, чем из 2*S + 1 человек (это правило может нарушаться только для одной группы - группы "главных помощников"). Все группы делятся на две категории. Помощники, состоящие в группах одной категории, непосредственно выполняют различные работы. Помощники же, состоящие в группах другой категории, выполняют роль посредников между группами (как одной, так и другой категории).
Ормус всегда носит темно-синий плащ, а "главные помощники" - темно-лиловые плащи. Помощники "главных помощников" вновь надевают темно-синие плащи, а их помощники, в свою очередь, темно-лиловые, и так далее.
Каждому помощнику выдается ник из 20 строчных латинских букв. Внутри группы помощники считаются упорядоченными по никам (по алфавиту, или лексикографически). Каждый помощник-посредник является посредником строго между двумя группами, в одной ("левой") из которых все ники лексикографически меньше его собственного, а в другой ("правой") - больше. "Правая" группа при этом будет "левой" для следующего (по алфавиту) помощника-посредника, а "левая" - "правой" для предшествующего.
Так, на рисунке (S = 2; ради компактности на нем использованы двухбуквенные ники) группы "непосредственных исполнителей" заключены в двойную рамку, группы посредников - в одинарную. Например, группа непосредственных исполнителей lf и lo является "правой" для помощника lb и "левой" для помощника lp. Сами же помощники lb и lp входят в группу, которая является "правой" для помощника ja и "левой" для помощника or. Помощники ja и or составляют группу "главных помощников".
Приход помощника.
Новый помощник сначала может стать только непосредственным исполнителем. Ормус выдает ему ник и отсылает его к группе "главных помощников". Те действуют следующим образом.
- Если их (без учета вновь пришедшего) уже 2*S + 1 человек, то средний (в смысле ника) объявляется единственным "главным помощником", который становится посредником между двумя вновь образовавшимися группами.
- Если же "главных помощников" на момент прихода нового меньше, чем 2*S + 1, то с группой "главных помощников" ничего не происходит.
После того, как "главные помощники" разобрались между собой, они определяют, к какой группе следующего уровня должен относиться ник вновь пришедшего, и отправляют его в эту группу. В этой группе также может произойти аналогичное разделение, и тот, чей ник оказался в середине списка, перейдет в группу уровнем выше на соответствующее нику место.
Процесс происходит до тех пор, пока новый помощник не придет в группу непосредственных исполнителей. Она при необходимости тоже делится, после чего новый помощник, наконец, оказывается включенным в эту группу или в одну из вновь образованных групп непосредственных исполнителей.
Уход помощника.
Случается, что кто-то из помощников перестает таковым быть. Первым об этом узнает Ормус и сообщает его ник группе "главных помощников". Их дальнейшие действия таковы. Сначала они выясняют, входит ник в их группу или нет.
- Если входит, его место должен занять кто-то другой.
- - Если в "левой" группе уходящего более S человек, то последний (лексикографически) ник из нее переходит в группу уровнем выше. Разумеется, "повышенному" придется искать замену аналогичным образом среди помощников уровнем ниже.
- - Если в "левой" группе состоит только S человек, но в "правой" их больше S, то уходящего заменит первый (лексикографически) ник из "правой" группы (и в его группе также придется искать ему замену).
- - Наконец, если и в "левой", и в "правой" группах содержится ровно по S человек, то эти группы объединяются, и замена уходящему не нужна.
- Если уходящий не входит в данную группу, то определяется, в какой группе помощников следующего уровня этот ник может содержаться, и она анализируется так, как описано выше.
Однако, поскольку должно поддерживаться свойство, что в группе (кроме группы "главных" помощников) должно быть не менее S (и не более 2*S + 1) ников, приходится анализировать, не произойдет ли при этом переход в группу, содержащую ровно S ников (тогда удаление из нее нарушит вышеуказанное свойство).
- Поэтому для группы следующего уровня выполняется такой анализ:
- - Если в эту группу входит более S человек, то следует перейти к рассмотрению этой группы и продолжить процедуру поиска удаляемого ника. Разумеется, из группы непосредственных исполнителей ник просто удаляется.
- - Если в эту группу входит ровно S человек, то просматриваются "соседние" группы, связанные с этой группой через посредника. Сначала - если таковая существует - рассматривается "левая" группа того посредника, для которого данная группа является "правой".
- - - Если в ней оказалось больше S ников, то последний ник из нее заменяет посредника, посредник уходит в данную группу, и процедура удаления может быть продолжена (так, как было описано выше). При этом посредник, уходящий в данную группу, становится посредником между никами из правой группы своего сменщика и никами из левой группы первого ника в данной (конечно, если речь не идет о группе непосредственных исполнителей, у которых нет своих групп).
- - - Если в ней оказалось ровно S ников, то рассматривается "правая" группа того посредника, для которого данная является "левой". Посредника меняет первый ник из нее, посредник уходит в данную группу, и процедуру удаления можно продолжать (так же, как описано выше). Посредник, ушедший в данную группу, станет посредником между никами из правой группы последнего ника в данной и никами из левой группы своего сменщика (опять же, если речь не идет о группе непосредственных исполнителей)
- - - Если в обеих "соседних" группах оказалось ровно по S ников, то данную группу объединяют с "правой соседней", посредник между ними также включается в новую объединенную группу, и процедура удаления может быть продолжена. Объединение с "левой соседней" происходит только при отсутствии "правой соседней".
По описанию групп помощников и последовательности ников приходящих и уходящих помощников требуется определить, сколько человек после всех изменений будут носить темно-синие плащи, а сколько - темно-лиловые.
Формат входного файла input.txt
Первая строка содержит три целых числа N, S и L через пробел (1 <= N <= 1000, 1 <= S <= 10, 1 <= L <= 25), N - общее количество групп помощников, S - минимальное количество помощников в группе, L - длина (в символах) каждого ника.
Далее идут описания групп помощников.
Сначала описывается группа главных помощников, затем - в порядке следования слева направо все группы следующего уровня, и т.д.
Каждое описание состоит из двух строк.
В первой строке записано число помощников в группе Pj (j = 1, 2, ..., N; S <= Pj <= 2*S + 1, j >= 2)
Во второй - Pj ников через пробел (каждый ник - последовательность символов длиной L, все ники уникальны)
Следующая строка после описания последней группы помощников содержит целое число K (0 <= K <= 2000) - суммарное количество добавленных или удаленных ников.
Каждая из следующих K строк содержит информацию о добавлении (+) или удалении (-) ника вида: "+<один пробел> <ник> или "-<один пробел><ник>". Добавления и удаления происходят именно в указанном порядке.
Формат выходного файла output.txt
Два целых числа B и R через пробел, B - количество помощников, носящих темно-синие плащи, R - количество помощников, носящих темно-лиловые плащи, после всех добавлений и удалений.
Пример входного файла
14 2 2
2
ja or
2
bj gt
3
lb lp no
2
st uv
2
ak ar
4
da eq ew fh
3
hk iu ix
3
ka kr la
2
lf lo
5
ma mc md mr ms
3
nx ny nz
5
pa pq qa ra sa
3
sz tg uk
2
xx yy
5
+ zz
- iu
- ix
+ dk
+ pr
Пример выходного файла
8 34