Задача №114891. Подарок для Луиджи
Однажды Марио решил сделать Луиджи подарок.
У Марио есть четыре палочки с положительными целочисленными длинами. Марио может разломать каждую палочку на несколько других. Длина каждой получившейся палочки также должна быть целым положительным числом, а их суммарная длина получается равной длине исходной палочки.
После этого Марио выбирает из получившихся палочек четыре таких, что из них можно составить прямоугольник, используя выбранные палочки в качестве его сторон. Каждая сторона должна целиком состоять ровно из одной выбранной Марио палочки.
Луиджи очень любит прямоугольники с большой площадью, поэтому Марио старается действовать так, чтобы получить прямоугольник наибольшей площади. Помогите ему найти такой прямоугольник.
В единственной строке записаны через пробел четыре целых положительных числа a , b , c , d — длины палочек, которые были у Марио исходно ( 1 ≤ a , b , c , d ≤ 10 15 ).
В единственной строке выведите через пробел два числа — длины сторон прямоугольника с наибольшей площадью, который может получить Марио, как-то разбив исходные палочки. Если ответов несколько, выведите любой из них.
Задача состоит из 51 теста. За каждый пройденный тест, кроме теста из условия, в данной задаче вы будете получать по 2 балла, тест из условия стоит 0 баллов.
Дополнительные ограничения:
- В 13 тестах a , b , c , d ≤ 50 .
- В 27 тестах a , b , c , d ≤ 10 5 .
- В 38 тестах a , b , c , d ≤ 10 9 .
В тесте из условия оптимальный ответ можно получить, если разбить вторую палочку на палочки длин 2 и 6, первую и третью оставить как есть, а четвертую разбить на три палочки с длинами 1, 9 и 9. Тогда взяв из этих палочек, палочки длин 6, 6, 9 и 9, мы сможем составить прямоугольник с длинами сторон 6 и 9, и площадь его будет оптимальной для этого теста.
1 8 6 19
9 6