408687: GYM103262 B Деревья на аллее
Description
Представим себе бесконечную аллею, которая идет вдоль оси $$$OX$$$ и начинается в точке $$$X=0$$$.
С каждой из сторон аллеи посажены деревья. С одной стороны деревья посажены в точках $$$A$$$, $$$A+B$$$, $$$A+2\cdot B$$$ и так далее, то есть в точках $$$A+N\cdot B$$$ для любого целого неотрицательного $$$N$$$. При этом $$$0 \leq A < B$$$. Аналогично, с другой стороны аллеи деревья посажены в точках $$$C$$$, $$$C+D$$$, $$$C+2\cdot D$$$ и так далее. При этом $$$0 \leq C < D$$$. Обратите внимание, что в некоторых точках может оказаться два дерева — по одному с каждой из сторон аллеи (см. пример 1).
Вася любит фотографировать деревья. Он хочет прогуляться по аллее и сфотографировать минимум $$$K$$$ деревьев. Однако, он может фотографировать дерево только если находится в одной точке с ним. Вася довольно ленив и хочет пройти вдоль аллеи наименьшее возможное расстояние. При этом он может начать движение в любой точке аллеи — он просто подъедет к ней на машине. Помогите Васе найти отрезок минимальной длины, который ему нужно пройти пешком, чтобы сфотографировать хотя бы $$$K$$$ деревьев.
Входные данныеВ первой строке заданы 4 целых числа: $$$A, B, C$$$ и $$$D$$$, $$$0 \leq A < B \leq 10^9$$$, $$$0 \leq C < D \leq 10^9$$$.
Во второй строке задано одно натуральное число $$$K$$$, $$$1 \leq K \leq 10^9$$$.
Выходные данныеВывести два целых числа $$$L$$$ и $$$R$$$ — концы отрезка аллеи, который нужно пройти Васе. Отрезок должен содержать хотя бы $$$K$$$ деревьев и иметь минимальную возможную длину. Несмотря на то что аллея бесконечная, вам нужно найти такие числа $$$L$$$ и $$$R$$$, что $$$0 \leq L \leq R \leq 8\cdot 10^{18}$$$. Гарантируется, что среди оптимальных ответов существует ответ, удовлетворяющий этим ограничениям. Если таких оптимальных ответов несколько, можно вывести любой из них.
Система оценкиПодзадача 1, 25 баллов: все входные числа не превосходят $$$5000$$$.
Подзадача 2, 25 баллов: все входные числа не превосходят $$$10^7$$$.
Подзадача 3, 50 баллов: дополнительных ограничений нет.
ПримерыВходные данные1 2 3 5 4Выходные данные
1 5Входные данные
0 2 1 2 6Выходные данные
1000 1005Примечание
В первом примере Вася может сфотографировать дерево в точке 1, два дерева в точке 3 и дерево в точке 5. Другой возможный оптимальный вариант — пройти от точки 5 до точки 9, длина пути так же будет равна 4. Более короткого маршрута, содержащего хотя бы 4 дерева, не существует.
Во втором примере в каждой точке находится ровно по одному дереву (с одной стороны деревья на четных позициях, с другой — на нечетных). Любой маршрут длины 5 будет содержать 6 деревьев.