Треугольник из палочек
INPUT.TXT OUTPUT.TXT
жүктеу/скачать 36,68 Kb.
|
Пояснение к примерам В первом примере газировки могло быть, например, 115 литров, в этом случае понадобится две емкости в 60 литров, а могло быть – 135 литров, в этом случае понадобятся уже три емкости по 60 литров. Четыре емкости не могут понадобиться никогда. Во втором примере легко видеть неточность в данных, так как количество ёмкостей по 70 литров не может превышать число ёмкостей по 50 литров (увеличение объёма используемых ёмкостей может только уменьшить их количество). Разделение прямоугольника (Время: 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. Пример
жүктеу/скачать 36,68 Kb. Достарыңызбен бөлісу:
|