0360. Освещение дома

Input file name: lighting.in
Output file name: lighting.out
Time limit: 2 s
Memory limit: 256 megabytes

Директор компании KTP SOLUTIONS проникся идеей светодиодных технологий. Теперь он хочет купить домой несколько светодиодных светильников квадратной формы, чтобы осветить всю свою большую комнату.

Комната при рассмотрении сверху представляет из себя прямоугольник со сторонами A и B. Высотой комнаты в данной задаче можно пренебречь. Светильник, будучи закреплённым на потолке, освещает некую квадратную область на полу, со стороной x, с центром в точке установки светильника.

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

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

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

В первой строке входного файла заданы три целых числа – A, B, N (1 ≤ A, B ≤ 10'000, 1 ≤ N ≤ 100), где A и B – размеры комнаты, а N – число типов светильников. Во второй строке перечислены N целых чисел xi в невозрастающем порядке (1 ≤ xi ≤ 100), где xi – размер стороны области, освещаемой светильником i-го типа.

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

В выходной файл выведите одно целое число – минимальное количество светильников, которое потребуется для освещения всей комнаты.

Пример:

lighting.inlighting.out
10 10 2 5 2 4
3 5 1 3 2



Discuss       Submit a solution



Printable version