Задача №1146. Карточный домик
Петя построил из карт домик, подобный тому, что изображен на рисунке. В нижнем ряду находится 2N карт.
Однако не успел Петя выйти из комнаты, как его младший брат Ваня подбежал к домику и вытащил одну из карт. В результате некоторые карты оказались в неустойчивом положении и осыпались. После этого еще несколько карт оказались неустойчивыми и осыпались. Этот процесс продолжался, пока не оказалось, что все оставшиеся карты стоят устойчиво. Когда Петя вошел в комнату. он с ужасом увидел, что от его домика осталось лишь жалкое подобие былого величия, а кучка карт лежит на столе.
После небольшой разборки Пете удалось выяснить, какую карту вытащил Ваня из его домика. Помогите Пете определить, сколько карт осыпалось в его домике, не считая их.
Формализуем некоторые понятия:
Скажем, что горизонтальная карта стоит устойчиво, если ее с обеих сторон подпирает хотя бы одна наклонная карта. Скажем, что наклонная карта стоит устойчиво, если снизу ее хотя бы с одной стороны подпирает горизонтальная карта, либо она стоит на столе, а сверху ее подпирает парная ей наклонная карта. Все остальные карты стоят неустойчиво.
Первая строка входного файла содержит число N (1 N 30000). Вторая строка содержит описание вынутой Ваней карты: первый символ – одна из букв H или V – задает направление карты в исходном домике (горизонтальное или наклонное соттветственно), затем следуют два числа – номер ряда, в котором лежала карта, считая сверху, начиная с 1 (счет ведется отдельно для горизонтальных и вертикальных рядов), и номер карты в этом ряду, считая слева, начиная с 1. Числа отделены от символа, задающего направление, и друг от друга пробелами.
Выведите в выходной файл единственное число – количество осыпавшихся карт (не считая вытащенной Ваней).
3 V 1 1
1
3 V 2 1
4
4 H 3 2
0