| Manthan, Codefest 16 |
|---|
| Закончено |
Стартап, связанный с торговлей в интернете, просит инвесторов о финансировании. Он работает уже n недель, и у него даже есть сайт!
Для каждой недели менеджеры стартапа знают количество уникальных посетителей vi и доход ci. Чтобы оценить потенциал стартапа в промежутке с недели l по неделю r включительно, инвесторы используют минимум из максимального количества посетителей, умноженного на 100, и минимального дохода в течение этого промежутка времени. Формально:
Стоит честно заметить, что инвесторы понятия не имеют, как эффективно оценить стартап, поэтому они выберут k случайных различных недель в качестве li и дадут эти числа менеджерам стартапа. Для каждого li те выберут некоторое ri ≥ li и сообщат инвесторам максимальное количество посетителей и минимальный доход в течение соответствующего периода с li по ri.
Затем инвесторы вычислят потенциал стартапа для каждого из данных промежутков времени и выберут минимальное значение p(li, ri) в качестве итоговой оценки потенциала стартапа. Предполагается, что менеджеры стартапа всегда оптимально выбирают значения ri для данных li, то есть таким образом чтобы максимизировать итоговую оценку стартапа, чему равняется математическое ожидание этой величины?
В первой строке входных данных записаны два числа n и k (1 ≤ k ≤ n ≤ 1 000 000).
Во второй строке записаны n целых чисел vi (1 ≤ vi ≤ 107) — количество уникальных посетителей за каждую неделю.
В третьей строке записано n целых чисел ci (1 ≤ ci ≤ 107) — доход стартапа за каждую неделю.
Выведите единственное вещественное число — математическое ожидание итоговой оценки стартапа. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.
А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если 
.
3 2
3 2 1
300 200 300
133.3333333
Рассмотрим первый пример.
Если инвесторы спросят про li = 1, менеджеры стартапа выберут ri = 1, так чтобы максимальное число посетителей равнялось 3, а минимальный доход равнялся 300. Таким образом потенциал будет равен min(3·100, 300) = 300.
Если инвесторы спросят про li = 2, менеджеры стартапа выберут ri = 3, так чтобы максимальное число посетителей равнялось 2, а минимальный доход равнялся 200. Таким образом потенциал будет равен min(2·100, 200) = 200.
Если инвесторы спросят про li = 3, менеджеры стартапа выберут ri = 3, так чтобы максимальное число посетителей равнялось 1, а минимальный доход равнялся 300. Таким образом потенциал будет равен min(1·100, 300) = 100.
Теперь нужно выбрать равновероятно множество размера 2, в каждом выбрать минимум. Возможные множества: {200, 300},{100, 300},{100, 200}. Оценки стартапа потенциалов получаются {200, 100, 100}. Таким образом, математическое ожидание (100 + 200 + 100) / 3 = 133.(3).
