Задача 2. Разделение прямоугольника ≡

Условие

Аня играет в новую настольную игру «Клетчатое королевство».

Рассмотрим прямоугольное клетчатое поле размером a × b.

Необходимо разделить его на m прямоугольников вертикальными или горизонтальными разрезами. Прямоугольники не обязательно должны получиться равными. Необходимо суммарно провести ровно k разрезов.

Каждый разрез представляет собой прямую линию от одного края поля до другого края поля. Разрезы разрешено делать только по границам клеток — линиям сетки.

Выведите, сколько провести горизонтальных (0 ≤ h < a) и сколько вертикальных (0 ≤ v < b) разрезов. Если поле можно разрезать несколькими способами, выведите тот, в котором горизонтальных разрезов меньше. Если поле нельзя разрезать требуемым образом, выведите  − 1.

Формат входных данных

В первой строке дано ровно одно целое число t — количество тестов.

В следующих t строках находится описание тестов: в i-й строке через пробел даны четыре целых числа: a, b, k, m — высота и ширина поля, количество разрезов и количество прямоугольников соответственно.

Формат выходных данных

Для каждого теста выведите через пробел ровно два целых числа h и v — количество горизонтальных и количество вертикальных разрезов, если прямоугольное клетчатое поле можно разрезать требуемым образом, в противном случае выведите число  − 1.

Ограничения

1 ≤ t ≤ 100

1 ≤ a, b ≤ 10⁹, 0 ≤ k ≤ 2 ⋅ 10⁹, 1 ≤ m ≤ 10¹⁸, k < m

Система оценки

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

Пояснение к примеру

В приведенном примере содержится три теста:

1. В первом тесте поле можно разрезать, как показано на рисунке:

   

2. Во втором тесте поле нельзя разрезать требуемым образом.
3. В третьем тесте поле можно разрезать, как показано на рисунке:

   

Примеры тестов

3
2 2 1 2
1 2 2 3
3 5 5 12

0 1
-1
2 3

Разбор

Автор задачи: Андрей Станкевич

Пусть было проведено x горизонтальных и y вертикальных разрезов (0 ≤ x < a, 0 ≤ y < b).

Подзадача 1

Так как по условию подзадачи a = 1, то единственно возможное количество горизонтальных разрезов x = 0. Тогда количество вертикальных разрезов y = k. Остается проверить: если выполняются условия k < b и m = k + 1, то можно провести x = 0 горизонтальных и y = k вертикальных разрезов так, чтобы получилось ровно m = k + 1 частей, в противном случае поле нельзя разрезать требуемым образом.

Асимптотика такого решения O(1).

Подзадачи 2 и 3

Переберем возможное количество горизонтальных разрезов x (0 ≤ x ≤ k), по возрастанию. Вычислим количество вертикальных разрезов y = k − x. Заметим, что если мы провели ровно x горизонтальных и ровно y вертикальных разрезов, то поле разделилось на p = (x + 1) ⋅ (y + 1) частей. Остается проверить: если p = m, то поле можно разрезать требуемым образом и мы нашли ответ {x, y}. Если для всех возможных x верно что p ≠ m, то поле нельзя разрезать требуемым образом.

Асимптотика такого решения O(k).

Подзадача 4

Аналогично предыдущей подзадаче хотим перебирать возможное количество горизонтальных разрезов x (0 ≤ x ≤ k). Будем делать это с учетом того, что число m должно делится на число x + 1. Для этого будем перебирать все делители числа m: пусть g — делитель числа m, тогда x = g − 1.

Асимптотика такого решения O(√m), так как чтобы перебрать все делители g числа m, достаточно перебирать их до корня (g ≤ √m).

Подзадача 5

Составим следующие уравнения: {x + y = k(x + 1) ⋅ (y + 1) = m

Выразим переменную y = k − x из первого уравнения и подставим во второе, получим: (x + 1) ⋅ (k − x + 1) = m

Раскроем скобки и приведем к стандартному виду: x ⋅ k − x² + x + k − x + 1 = m  − 1 ⋅ x² + k ⋅ x + (k − m + 1) = 0

Это квадратное уравнение относительно переменной x вида: A ⋅ x² + B ⋅ x + C = 0 где коэффициенты равны соответственно A =  − 1, B = k, C = k − m + 1.

Вычислим дискриминант квадратного уравнения по известной формуле: D = B² − 4 ⋅ A ⋅ C = k² − 4 ⋅ ( − 1) ⋅ (k − m + 1) = k² + 4 ⋅ (k − m + 1)

Если полученный дискриминант меньше нуля D < 0 или не существует целого числа q, такого что выполняется равенство q² = D, то значит поле нельзя разрезать требуемым образом.

В противном случае вычислим целое число q = √D, а затем найдем два решения квадратного уравнения x₁ и x₂, и соответствующие им y₁, y₂: x₁ =  − B − √D2 ⋅ A = k + q2,   y₁ = k − x₁ x₂ =  − B + √D2 ⋅ A = k − q2,   y₂ = k − x₂.

Остается проверить, какое из решений {x_i, y_i}, где i = {1, 2}, подходит под ограничения: 0 ≤ x_i < a  и  0 ≤ y_i < b  и  x_i, y_i ∈ Z и выбрать его в ответ. В случае, если под ограничение подходят оба решения, необходимо выбрать в ответ то из них, где количество горизонтальных разрезов x_i минимально.

Асимптотика такого решения O(1).