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

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

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

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

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

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

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

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

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

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

Пример:

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

Источник: Муниципальный этап всероссийской олимпиады школьников по информатике, 2013-2014 учебный год

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