Сортировка дробных чисел

Задача:
Жил себе мирно в лесу мальчик Вася, но беды приходят неожиданно. С горы падают камни. Изначально Василий находится на интервале [0, 1]. Потом упадут n камней, а Вася будет убегать от камней. Камни последовательно пронумерованы от 1 до n в порядке их падения.
Камни всегда падают точно в центр интервала Василия. Когда Вася занимает интервал [k - d, k + d] и камень падает в точку k, мальчик бежит налево или направо. Если он убежит налево, его новый интервал будет [k - d, k]. Если побежит направо, его новый интервал будет [k, k + d].
Вам дана строка s длины n. В строке s i-ый символ — это либо «l», либо «r», то есть, когда падает i-ый камень, Василий побежит налево или направо, соответственно. Найдите последовательность номеров камней слева направо после того, как упадут все n камней.
Решение задачи ясно как день, опишу его и проблему с сортировкой дробных чисел:
l,r- левая и правая границы интервала(изначально они равны 0 и 1 соответственно)
Идем по всем символам строки, если i-й символ это 'l' то k=(l+r)/2; d=(r-k); l=k-d; r=k; и в словарь(например) запишем пару (i+1,k),где i+1 будет номером камня,k-его координата
если i-й символ это 'r' то k=(l+r)/2; d=(r-k); l=k; r=k+d; и в словарь запишем пару (i+1,k)
В конце надо отсортировать все пары по k, и после вывести все номера камней.
Проблема в том, что для строк длины больше 300(примерно) значения k в словаре выходят с огромным количеством знаков после запятой, а тип float столько знаков не может хранить, и отсекает большую часть, в итоге чего сортировка выходит неверная.
Возможно ли реализовать такую сортировку, если вместо float использовать тип Decimal(там вроде как почти не ограничено кол-во знаков), и если да, то как?

0

fractions

0