ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование школьников. Октябрь 2002

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Морской бой

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Однажды в школе на уроке информатики Петя и Вася решили сыграть в морской бой. Заканчивая расставлять свои корабли на листочке, Петя задумался: ему вдруг стало интересно, сколькими различными способами он сможет поставить свой последний K-палубный кораблик? Он попробовал быстро посчитать количество способов, но скоро сбился со счета. Тогда Петя посмотрел по сторонам и, неожиданно для себя, увидел стоящие повсюду компьютеры (в этом нет ничего удивительного, ведь, как мы помним, дело было на уроке информатики; но до этого момента Петя был так увлечен подготовкой к игре, что компьютеров не замечал). Подумав немного, он решил написать программу, которая может решить его задачу. Но у него ничего не получилось, поскольку он был двоечником — он отнюдь не первый раз в своей жизни играл в морской бой на уроке! Помогите Пете в его нелегком деле.

Исходные данные

Problem illustration
В первой строке содержатся три числа, разделённые пробелами: размер поля по вертикали N (1 ≤ N ≤ 30000), размер поля по горизонтали M (1 ≤ M ≤ 30000) и количество уже поставленных кораблей L (0 ≤ L ≤ 30). Далее следуют L строк с описанием расставленных кораблей. Описание каждого корабля состоит из записанных через пробел трёх чисел и буквы. Числа — это координаты левого верхнего угла корабля (левая верхняя клетка игрового поля имеет координаты (1, 1)) и количество палуб корабля. Буква же задает ориентацию корабля («V» — если корабль стоит вертикально и «H» — если горизонтально). В последней строке содержится число K — количество палуб корабля, который нужно поставить Пете.
Для тех, кто никогда не играл в морской бой, поясним, что i-палубный корабль — это прямоугольник размером i × 1 клеточку. Корабли могут иметь от одной до четырёх палуб. По правилам игры корабли не могут касаться друг друга рёбрами или вершинами.

Результат

Выведите количество различных способов, которыми Петя может разместить на поле K-палубный корабль.

Пример

исходные данныерезультат
4 4 2
1 2 2 V
3 1 2 H
2
4
Автор задачи: Антон Ботов и Анатолий Углов
Источник задачи: USU Open Collegiate Programming Contest October'2002 Junior Session
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1212. Морской бой