I. Плитка

Имя входного файла:	tiles.in
Имя выходного файла:	tiles.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Леонард и Шелдон затеяли ремонт в квартире. Сейчас они ремонтируют ванную комнату и хотят выложить стену кафельной плиткой. Шелдон уже составил <<Соглашение о плитке>>, а Леонард как обычно его не глядя подписал. В Соглашении Шелдон указал следующее:

1. Стена для выкладывания представляет собой прямоугольник размером w*h сантиметров.
2. Каждая плитка представляет собой квадрат размера a*a сантиметров.
3. Стена должна быть полностью покрыта плиткой. Шириной швов между плитками можно пренебречь.
4. Плитки можно резать только параллельно сторонам. Одну плитку можно разрезать несколько раз.
5. При использовании разрезанных плиток их нужно укладывать так, чтобы линии разреза плиток совпадали с краями стены (другими словами, нельзя допускать того, чтобы линии разреза были внутри стены.

Леонард уже и сам не рад, что подписал такое соглашение. Теперь ему требуется собственно закупить плитку, но он не знает, какое минимальное количество плиток требуется для замощения стены. Помогите ему найти это количество.

Формат входного файла

Во входном файле находятся три целых числа: w, h, a – размеры стены и плиток соответственно (1 ≤ w, h, a ≤ 1000).

Формат выходного файла

Выведите единственное число – минимально возможное количество плиток, которое должен купить Леонард.

Пример:

tiles.in	tiles.out
2 2 1	4
4 4 3	3
5 5 3	4

На рисунках показано расположение плиток в оптимальном случае во всех примерах. Обратите внимание, что во втором примере для замощения угла приходится использовать отдельную плитку, поскольку разрезанные части плиток должны совпадать с краями стен.

Источник: Первенство первокурсника ПетрГУ. Май 2012

Обсудить       Отправить решение