Полагодження паркану#1529
Вам потрібно полагодити старий паркан, що складається з ряду дощок, деякі з яких зламані. Дошки пронумеровані зліва направо у порядку зростання.
Полагодження всіх дощок з -ї по -ту включно (де i \leq j) коштує \sqrt{j - i + 1}. Щоб зменшити загальні витрати на ремонт, іноді вигідно ремонтувати навіть цілі дошки. Ваше завдання — знайти мінімальну вартість ремонту всього паркану.
Дано інформацію про паркан. Зламані дошки позначаються символом X, а цілі — символом .. Знайдіть мінімальну вартість ремонту всього паркану.
Кожен рядок представляє окремий тест, що описує стан паркану. Він складається лише з таких символів:
X — зламана дошка;
. — ціла дошка;
Довжина рядка (паркану) не перевищує символів.
Для кожного тесту в окремому рядку виведіть мінімальну вартість ремонту всього паркану з точністю до знаків після коми.
Приклад 1