0279. Сковородки

Имя входного файла:	pans.in
Имя выходного файла:	pans.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Большинство людей воспринимают эстетику довольно близко к сердцу: некоторым не нравятся предметы, лежащие не под прямыми углами, некоторым – просто углы, так и Говард Воловиц имеет обычай выравнивать сковородки, расположенные друг на друге, относительно положения их ручек. Небызвестная маман часто заставляет его мыть посуду. Иногда, ему приходится мыть такое количество сковородок, что выравнивание вызывает у него головную боль и он вконец запутывается.

Итак, Говард помыл n сковородок, первая из которых стоит на столе, а каждая i-ая (2 ≤ i ≤ n) располагается внутри (i - 1)-ой так, что их центры совпадают. Если посмотреть сверху, можно увидеть круг, из которого в разные стороны торчат ручки. Говард хочет повернуть некоторые сковородки так, чтобы все ручки торчали из стопки в одну сторону.

Обозначим α_i – угол поворота ручки i-той сковородки относительно какого-нибудь (одного) направления из центра координат в радианах. Центр координат расположен в центре первой (да и любой другой тоже) сковородки. Говард может повернуть любую сковородку на произвольный угол β в радианах, при этом на тот же угол поворачиваются все сковородки расположенные на той, которую он поворачивает. Ввиду большого количества сковородок, Говард хочет выровнять их за минимальное время. При повороте сковородки на угол β Говард тратит β времени.

Помогите Говарду, составьте оптимальный план поворотов сковородок, требующий минимальные затраты по времени.

Формат входного файла

В первой строке входного файла задано целое число n – количество сковородок (1 ≤ n ≤ 10⁵). Во второй строке находится n вещественных чисел α_i – угол поворота α_i ∈[0, 2π) ручки i-ой сковородки (1 ≤ i ≤ n). Углы поворота заданы не более чем с тремя знаками после запятой.

Формат выходного файла

Выведите единственное число – минимальное время, требуемое Говарду на преодоление трудности, связанной с неэстетичным расположением сковородок. Ваш ответ будет считаться правильным, если он отличается не более, чем на 10^-6, по абсолютной или относительной величине.

Пример:

pans.in	pans.out
3 0.5 0.234 0.234	0.266
3 0.5 0.2 0.1	0.4

Источник: Первенство первокурсника ПетрГУ. Май 2012

Обсудить       Отправить решение



Версия для печати