697. Коробка
Кондитерской
фабрике нужны коробки для шоколада, которые необходимо сделать из картонных
листов размером axa. Коробка должна быть открытой сверху и
иметь квадратное основание. Коробка формируется в два этапа. На первом шаге
квадратные кусочки размера bxb вырезаются из углов картонного листа.
На втором шаге прямоугольные части сгибаются на 90 градусов внутрь коробки. По
длине стороны картонного листа a
необходимо найти такую высоту b
коробки, для которой ее объем будет максимальным.
Вход. Первая строка содержит количество тестов n (1 ≤ n ≤ 10). Каждая из следующих n строк является отдельным тестом и содержит одно действительное
число – длину стороны картонного листа a (1
≤ a ≤ 1014).
Выход. Вывести n строк, каждая из которых содержит
оптимальную высоту b для
соответствующего теста, округленная до 10 знаков после запятой.
|
Пример
входа |
Пример
выхода |
|
1 34.0 |
5.6666666667 |
РЕШЕНИЕ
математика
Анализ алгоритма
Длина основания
коробки равна a – 2b. Площадь основания коробки равна (a – 2b)2
, а ее объем (a – 2b)2 * b.
Найдем максимум функции f(b) = (a – 2b)2 * b.
f’(b) = 2(a – 2b) * (-2) * b
+ (a – 2b)2 = 0. Корень a
= 2b нам не подходит, так как коробка
в таком случае будет вырожденная. Имеем: -4b
+ a – 2b = 0, a = 6b, b
= a / 6.
То есть при b = a
/ 6 объем коробки будет наибольшим.
Реализация алгоритма
Для каждолго
теста читаем значение a и выводим a / 6.
scanf("%d",&n);
for(i = 0; i < n; i++)
{
scanf("%lf",&a);
printf("%.10lf\n",a/6);
}
Java реализация
Реализация через
сканер. Во входных данных символ перевода на новую строку ('\n') кодируется
одним байтом 0A как в Линуксе.
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
con.useLocale(new Locale("US"));
for(int i = 0; i < n; i++)
{
double a = con.nextDouble();
System.out.format(Locale.US,"%.10f\n",a/6);
}
}
}
Реализация через
BufferedReader.
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args)
throws Exception
{
BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
for(int i = 0; i < n; i++)
{
double a = Double.parseDouble(in.readLine());
System.out.format(Locale.US,"%.10f\n",a/6);
}
}
}