Разделение прямоугольника
(Время: 1 сек. Память: 32 Мб Сложность: 24%)
Ира играет в настольную игру «Клетчатое Герцогство».
Рассмотрим прямоугольное клетчатое поле размером a × b.
Необходимо разделить его на m прямоугольников вертикальными или горизонтальными разрезами. Прямоугольники не обязательно должны получиться равными. Необходимо суммарно провести ровно k разрезов.
Каждый разрез представляет собой прямую линию от одного края поля до другого края поля. Разрезы разрешено делать только по границам клеток – линиям сетки.
Выведите, сколько провести горизонтальных (0 ≤ h < a) и сколько вертикальных (0 ≤ v < b)
разрезов. Если поле можно разрезать несколькими способами, выведите тот, в котором горизонтальных разрезов меньше. Если поле нельзя разрезать требуемым образом, выведите -1.
Входные данные
В первой строке входного файла INPUT.TXT дано ровно одно целое число t – количество тестов (1 ≤ t ≤ 100).
В следующих t строках находится описание тестов: в i-й строке через пробел даны четыре целых числа: a, b, k, m – высота и ширина поля, количество разрезов и количество прямоугольников соответственно (1 ≤ a, b ≤ 109, 0 ≤ k ≤ 2×109, 1 ≤ m ≤ 1018, k < m).
Выходные данные
Для каждого теста в выходной файл OUTPUT.TXT в отдельной строке выведите через пробел ровно два целых числа h и v – количество горизонтальных и количество вертикальных разрезов, если прямоугольное клетчатое поле можно разрезать требуемым образом, в противном случае выведите число -1.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
2 2 1 2
1 2 2 3
3 5 5 12 | 0 1
-1
2 3 |
Пояснение к примеру
В приведенном примере содержится три теста:
1) В первом тесте поле можно разрезать, как показано на рисунке:
Иллюстрация к первому тесту:
a = 2, b = 2, k = 1, m = 2.
|
2) Во втором тесте поле нельзя разрезать требуемым образом.
3) В третьем тесте поле можно разрезать, как показано на рисунке:
Иллюстрация к третьему тесту:
a = 3, b = 5, k = 5, m = 12.
|
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
