Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






01

URL первоисточника: http://ctddev.ifmo.ru/school/io/archive.html

Задачу добавил: alef

Успешно сдано решений: 38

Задана строка длины N, состоящая из символов 0 и 1. Необходимо с помощью
последовательности обменов привести ее к такому виду, что сначала идут все символы 0, а затем идут все символы 1. Каждый обмен можно задать парой различных чисел i,j (1 <= i < j < = N). За каждый такой обмен назначается штраф, равный sqrt(j-i).

 Какой минимальный суммарный штраф придется уплатить за выполнение поставленной задачи?

Формат входного файла
Во входном файле записана заданная строка. Длина строки не менее 1 символа и не превосходит 4000 символов.

Формат выходного файла
Выведите искомый минимальный штраф с округлением до 5 знаков после запятой

Пример входного файла
100

Пример выходного файла
1.41421

Сдать задачу

Задать вопрос жюри по этой задаче