Экипировка
Автор задачи: Елена Рогачева, Александр Ефимов
Задачу добавил: alef
Успешно сдано решений: 1
Приключения агента 008
С давних пор компания Doors очень интересовалась разработками компании
Closed Systems в области новых операционных систем. И чтобы больше узнать
об этих разработках, руководство компании Doors посылало в компанию Closed
Systems своих лучших секретных агентов. Но им так и не удавалось узнать самые
секретные коды этих систем. И тогда было решено поручить это дело самому
секретному агенту. Конечно, мы не можем раскрыть его настоящее имя.
И поэтому будем называть его Агент 008.
Для выполнения такого секретного задания Агенту 008 нужно было изготовить
специальный костюм из специальной влагонепроницаемой, огнеупорной,
пуленепробиваемой (и, конечно же, легкой и приятной на ощупь) ткани,
со множеством потайных карманов, начиненный различными специальными
устройствами. И при этом никто не должен был подумать, что этот костюм
- специальный. Более того, на всякий случай желательно было бы изготовить
несколько таких костюмов. Лучшие закройщики взялись за дело. И тут возникла
одна проблема - такой специальной ткани было довольно мало.
Поэтому необходимо разместить детали кроя так, чтобы из данного куска ткани
можно было сшить как можно больше костюмов. Детали кроя могут быть либо
прямоугольными
треугольниками, либо прямоугольниками. При этом технология выкройки
такого костюма позволяет вырезать эти детали только так чтобы их
стороны (в случае прямоугольного треугольника-катеты) были параллельны
сторонам исходного куска ткани.
Формат входного файла input.txt
Первая строка - три целых числа M, N и K - длина и ширина куска ткани
в сантиметрах и количество деталей кроя (0<= M, N <= 100000; 1<=K<=100)
Следующие K строк содержат информацию о каждой из деталей кроя, при
этом
вначале идет одна буква P если это прямоугольник, T если треугольник,
прямоугольник задается двумя сторонами L1, L2 (0<=L1, L2<=1000);
а прямоугольный треугольник - двумя катетами L1, L2 (0<=L1, L2<=1000)
Формат выходного файла output.txt
целое число - количество костюмов, которое можно сшить из данного куска ткани
Пример входного файла
10 10 3
P 10 4
T 10 1
T 10 1
Пример выходного файла
2