| Автор: | Методическая комиссия по информатике | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
На координатной плоскости задан прямоугольник, высота которого h, а ширина — w. Внутри прямоугольника задано n отрезков, параллельных осям координат.
Прямоугольник планируется разрезать на несколько частей горизонтальными или вертикальными разрезами. За один шаг разрешается разрезать на две непустые прямоугольные части только один из имеющихся на этом шаге прямоугольников. Размеры получившихся частей должны быть целочисленными. Линия разреза не должна пересекать ни один из заданных отрезков.
Требуется написать программу, позволяющую найти количество способов разрезания исходного прямоугольника на k частей. Способы, отличающиеся порядком проведения разрезов, считаются различными.
1 ≤ h, w ≤ 8
1 ≤ k ≤ h × w
0 ≤ n ≤ 10
0 ≤ X1 ≤ X2 ≤ w, 0 ≤ Y1 ≤ Y2 ≤ h
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|