Задача B. Островки
Задачу добавил: alef
Успешно сдано решений: 8
Периодически приходится изготавливать новые брелоки для сотрудников НИИ — то в порядке плановой замены, то ввиду приема на работу нового сотрудника, то — при переводе сотрудника в другой отдел. Для проектирования брелоков, в частности, существует программа, формирующая описание позиций для квадратиков, содержащих чипы. Поскольку, как правило, допустимых позиций для размещения квадратиков с чипами больше, чем собственно таких квадратиков, такое описание (по которому впоследствии изготавливается брелок) не является единственно возможным.
Поэтому некоторые сотрудники запускают программу несколько раз, чтобы получить то описание, которое покажется им более симпатичным, если рассматривать его как геометрический узор.
Кеша Канарейкин находит симпатичными брелоки, в которых много "островков".
Назовем островком такую группу квадратиков, не содержащих чипы, для которой выполняются следующие условия:
1) каждый квадратик островка имеет общую сторону еще хотя бы с одним квадратиком этого же островка (исключение составляют островки, состоящие из единственного квадратика)
2) ни одна сторона ни одного из квадратиков островка не является границей брелока.
Когда Кеша получает описание своего нового брелока, он хочет знать, сколько "островков" на нем окажется.
Ваша задача — написать программу, определяющую количество "островков" по заданному описанию брелока. Также нужно вывести площади островков в невозрастающем порядке.
Формат входного файла input.txt
Первая строка - целое число N (1 <= N <= 10000) — количество квадратиков, укладывающихся вдоль стороны квадратного брелока
Следующие N строк содержат описания рядов квадратиков в следующем формате.
Первый символ в строке — C или E — в зависимости от того, содержит или нет чип первый квадратик в этом ряду. Затем через пробел следуют целые числа (не превосходящие N), указывающие количество квадратиков в очередной группе (либо содержащих, либо не содержащих чипы; разумеется, группы чередуются).
Формат выходного файла output.txt
Первая строка — целое число M — количество островков, за ним M целых чисел через пробел — площади островков, упорядоченные по невозрастанию.
Пример входного файла
10
C 3 2 5
C 5 2 3
C 5 2 3
C 10
E 2 5 2 1
C 2 2 3 2 1
C 2 1 4 2 1
C 10
C 7 2 1
C 10
Пример выходного файла
4 6 4 3 2