Məsələlər
Починка забора
Починка забора
Вам необходимо починить старый забор. Забор состоит из набора досок, некоторые из которых выломаны. Доски пронумерованы слева направо в возрастающем порядке. Починка всех досок от $i$-ой до $j$-ой включительно, где $j$ больше или равно $i$, стоит $\sqrt{j - i + 1}$. Для уменьшения общей стоимости ремонта иногда выгодно ремонтировать даже целые доски. Найдите минимальную стоимость ремонта всего забора.
Вам задана информация о заборе. Сломанные доски обозначаются символами "\textbf{X}", а целые символами "\textbf{.}". Найдите наименьшую стоимость починки всего забора.
\InputFile
Каждая строка является отдельным тестом, описывающей забор. Она содержит только символы "\textbf{X}" и "\textbf{.}". Длина каждого забора не более $2500$ символов.
\OutputFile
Для каждого теста в отдельной строке выведите наименьшую стоимость починки всего забора с $4$ десятичными цифрами.
Giriş verilənləri #1
X.X...X.X X.X.....X X.............XX.X.......X...X..
Çıxış verilənləri #1
3.0000 2.7321 5.0000