FLOOR
-
Ремонт пола
REPAIR OF A FLOOR
Теория
Это
было
примерно
так ...
Некий
господин
переехал в
новую
квартиру,
что
находилась
в районе "Цветочки".
Да вот беда:
пол в одной
из комнат
квартиры
оказался
плохо
настеленным
и
постоянно "скрипел"
и "визжал". Первой
не
выдержала
супруга и
приобрела
паркетные
плитки
одного и
того же
размера и
цвета.
Придя
домой с
работы, и
увидев в
коридоре
аккуратно
сложенные
стопки
плит,
супруг
вздохнул и ...
наметил
свой
воскресный
день
провести
не на
рыбной
ловле, а в
душной
комнате. Но
в начале он
должен был
выяснить:
достаточно
ли плиток
приобрела
супруга и
можно ли, не
разрезая
ни одной из
них,
застелить
весь пол в
комнате
так, чтобы
ни одна из
плиток не
перекрывала
другую.
Задача
Составьте программу FLOOR, определяющую, можно ли Q (1<=Q<=100.000) прямоугольными плитками, каждая из которых размером LxK (0<L, K<=10), застелить без перекрытия прямоугольный участок пола размером MxN (10<=M, N<=10.000).
Технические
требования:
Входной
файл: FLOOR.DAT
Выходной файл: FLOOR.SOL
Ограничение по времени тестирования: до 5 секунд на один тест
Входной файл: содержит построчно целые числа:
-
в первой строке - число плиток Q;
-
во второй строке - размеры плитки L и K;
-
в третьей строке - размеры пола M и N.
Выходной файл: выходной файл может состоять из двух строк, если приобретено достаточное количество плиток и ими можно застелить весь пол. В первой строке - единственное слово "OK", во второй - использованное количество плиток.
Если приобретенное количество плиток оказалось недостаточным, то файл должен содержать строку со словом "NO".
Если плиток достаточно, но невозможно ими застелить весь пол согласно предложенным условиям, то вывести величину оставшейся не застеленной площади пола. Лучшим считается решение, дающее минимальную оставшуюся площадь не застеленного пола.
Пример:
FLOOR.DAT
15
1 2
5
5
OUTPUT.TXT
1
Замечание:
резать
плитку
нельзя по
причине
отсутствия
инструмента
для резки.