Задача №111889. Гаражи
Ваша компания только что выиграла контракт на постройку гаражей. Строительная площадка представляет собой прямоугольник \(W \times H\), вам надо построить на нем гаражи. Гараж представляет собой прямоугольник \(w \times h\), его стороны параллельны сторонам стройплощадки (вращать гаражи нельзя, даже на 90 градусов). Координаты гаража могут быть нецелыми.
Вы хотите сэкономить, так что Вы хотите построить как можно меньше гаражей. Однако в контракте указано противоположное требование: построить максимально возможное количество гаражей.
Строительный план удовлетворяет контракту, если невозможно добавить новый гараж без передвижения старых.
Оптимальное корректное размещение
Некорректное размещение
Неоптимальное корректное размещение
Найдите минимальное число гаражей, которое должно быть построено.
Первая и единственная строка содержит четыре целых числа: \(W\), \(H\), \(w\), \(h\) – размеры стройплощадки и гаража (\(1 \leq w \leq W \leq 30000\), \(1 \leq h \leq H \leq 30000\)).
Выведите оптимальное число гаражей.
11 4 3 2
2
10 8 3 4
2