VK Cup 2012 Раунд 2 |
---|
Закончено |
Вася хочет купить новый холодильник. Он считает, что холодильник должен быть прямоугольным параллелепипедом с целочисленными длинами ребер. Вася рассчитал, что для повседневного пользования ему понадобится холодильник объема не меньше V. Кроме того, Вася по натуре минималист, поэтому объем должен быть и не больше V — к чему занимать лишнее место в квартире? Определившись с объемом холодильника, Вася столкнулся с новой непростой задачей — чтобы холодильник было проще мыть, при фиксированном объеме V он должен иметь минимальную площадь поверхности.
Объем и площадь поверхности холодильника с ребрами a, b, c равны V = abc и S = 2(ab + bc + ca), соответственно.
Помогите Васе по заданному объему V найти такие целые длины ребер холодильника a, b, c, чтобы объем холодильника был равен V и при этом его площадь поверхности S была минимальна.
В первой строке записано единственное целое число t (1 ≤ t ≤ 500) — количество наборов данных.
Далее следует описание t наборов данных. Каждый набор состоит из одного целого числа V (2 ≤ V ≤ 1018), заданного своим разложением на множители следующим образом.
Пусть V = p1a1p2a2... pkak, где pi — различные простые числа, а ai — положительные целые степени.
Тогда в первой строке описания набора данных записано единственное положительное целое число k — количество различных простых делителей V. В следующих k строках записаны простые числа pi и их степени ai, разделенные пробелом. Все pi различны, все ai > 0.
Выведите t строк, в i-й строке выведите ответ на i-й набор данных — четыре целых числа, записанные через пробел: минимальная возможная площадь поверхности S и соответствующие длины ребер a, b, c. Если вариантов длин ребер, дающих минимальную площадь, несколько, разрешается вывести любой из них. Длины ребер холодильника разрешается выводить в любом порядке.
3
1
2 3
1
17 1
3
3 1
2 3
5 1
24 2 2 2
70 1 1 17
148 4 6 5
В первом наборе данных примера объем холодильника V = 23 = 8, и минимальную площадь поверхности дадут ребра одинаковой длины.
Во втором наборе данных объем V = 17, и его можно получить из единственного набора ребер целочисленных длин.
Название |
---|