0
0 комментариев

Алена играет в настольную игру «Огромное Поле». Рассмотрим прямоугольное клетчатое поле размером a × b.
Необходимо разделить его на m прямоугольников вертикальными или горизонтальными разрезами. Прямоугольники не обязательно должны получиться равными. Необходимо суммарно провести ровно k разрезов. Каждый разрез представляет собой прямую линию от одного края поля до другого края поля.
Разрезы разрешено делать только по границам клеток — линиям сетки. Выведите, сколько провести горизонтальных (0 6 h < a) и сколько вертикальных (0 6 v < b) разрезов. Если поле можно разрезать несколькими способами, выведите тот, в котором горизонтальных разрезов меньше. Если поле нельзя разрезать требуемым образом, выведите −1.
Формат входных данных
В первой строке дано ровно одно целое число t — количество тестов (1 <= t <= 100). В следующих t строках находится описание тестов: в i-й строке через пробел даны четыре целых числа: a, b, k, m — высота и ширина поля, количество разрезов и количество прямоугольников соответственно (1 <= a, b <= 10^9, 0 <= k <= 2 · 10^9, 1 <= m <= 10^18, k < m).
Формат выходных данных
Для каждого теста выведите через пробел ровно два целых числа h и v — количество горизонтальных и количество вертикальных разрезов, если прямоугольное клетчатое поле можно разрезать
требуемым образом, в противном случае выведите число −1.

Arnfinn изменил статус на опубликованный 24.01.2023